题目内容

采草莓机器人在一个$n*m$的草莓矩阵内，从起点坐标$(0，0)$出发，可以向右或向下两个方向移动，每个方格种植着不同价值的草莓，现在小红规定了一个阈值$g$,代表该机器人此行采集草莓的总价值的最低目标值，小红想知道机器人计算完成任务所需要移动的最少移动次数可以满足这个阈值？

输入描述

第一行输入三个整数:$n,m,g$ , 以空格隔开。

题解：动态规划

由于只能向右和向下走，因此，对于坐标$(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]\ge g$，则可以更新最小步数，最小步数即为$(0,0$与$(i,j)$的曼哈顿距离值$dist=i+j$，其中$0\le i\le n,0\le j \le m$