题解 | #礼物的最大价值#

class Solution {
public:
  // 最大礼物，也就是累计走过的格子数值之和最大.注意，只能向右和向下走，这信息很重要
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        if(grid.empty()) return 0;//没有格子，值为0
        int m = grid.size();//行数
        int n = grid[0].size();// 列数
        for(int i = 1; i < m; ++i)// 算一下往下走时，每个格子的礼物数；为啥这么算？因为动态规划记录上一次走过的结果，而往下走，格子只能保留顶上路径数值
        {
            grid[i][0] = grid[i][0] + grid[i-1][0];
        }
        for(int i = 1; i < n; ++i)// 一直向右走，这么算的理由类似上一句，因为只有左侧来路数值
        {
            grid[0][i] = grid[0][i] + grid[0][i-1];
        }
        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                grid[i][j] = grid[i][j] + max(grid[i][j-1], grid[i-1][j]);//算一下，上侧还是左侧来车值更大，谁大选谁
            }
        }
        return grid[m-1][n-1];//达到终点，值最大
    }
};