题解60 | 矩阵的最大（最小）路径和#礼物的最大价值#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int r = grid.size();
        int c = grid[0].size();

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (i == 0 && j > 0) {//最上一行
                    grid[i][j] += grid[i][j-1];
                }else if (j == 0 && i > 0) {//最左一列
                    grid[i][j] += grid[i-1][j];
                }else {
                    if (i == 0 && j == 0) {
                        continue;
                    }

                    int max_value = max(grid[i-1][j],grid[i][j-1]);
                    grid[i][j] += max_value;

                }
            }
        }
        return grid[r - 1][c - 1]; //路径上所有的数字累加起来就是路径和。
    }
};

算法基本思想：

动态规划。从左上角开始遍历矩阵，对于每个位置，计算到达该位置的最大（最小）路径和，即为该位置的值加上上方和左方位置中较大（较小也一样：NC59矩阵的最小路径和）的值。最终返回右下角位置的最大（最小）路径和。

https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=196&tqId=37157&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj&difficulty=3&judgeStatus=undefined&tags=578&title=

时间复杂度：O(mn)，其中m为矩阵行数，n为矩阵列数，需要遍历整个矩阵。

空间复杂度：O(1)，只使用常数个额外变量。