动态规划问题:当前点的状态只能从上方的点或左边的点转换而来。
这题跟 1015. 摘花生 很像
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1)); //格式要统一用二维vector
//如果用f[n][m]会出错
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
return f[n][m];
}
};