剑指 Offer 47. 礼物的最大价值-526互联

方法：动态规划

解题思路

\(当前位置的最大价值 = max(上方格子的最大价值，左边格子的最大价值) + 当前位置的价值\)，即局部最优可以推出全局最优，简单递推即可。

代码

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for (int x = 1; x < m; x ++ ) grid[x][0] += grid[x - 1][0];
        for (int y = 1; y < n; y ++ ) grid[0][y] += grid[0][y - 1];
        for (int x = 1; x < m; x ++ )
            for (int y = 1; y < n; y ++ ) 
                grid[x][y] += max(grid[x - 1][y], grid[x][y - 1]);
        return grid[m - 1][n - 1];
    }
};

复杂度分析

时间复杂度：\(O(nm)\)；
空间复杂度：\(O(1)\)。