会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
题解：动态规划
由于只能向右和向下走，因此，对于坐标(i,j)，它一定是由(i−1,j)或者(i,j−1)位置移动得到，因此定义f[i][j]为走到(i,j)位置所获得价值的最大值，则有
f[i][j]=max(f[i−1][j],f[i][j−1])+w[i][j]
最终，枚举每一个点所获得价值的最大值，如果有f[i][j]≥g，则可以更新最小步数，最小步数即为(0,0与(i,j)的曼哈顿距离值dist=i+j，其中0≤i≤n,0≤j≤m
