[Lc]面试题47礼物的最大价值

题目

题解

这道题感觉做过类似的，忘了是哪一道了，反正就是原地动态规划，原地更新数组，边界直接加上左（或上）的数，中间的加左或上中比较大的数比较简单，具体可以看注释

• 时间复杂度$O(mn)$
• 空间复杂度$O(1)$

class Solution {//动态规划
public:
    int maxValue(vector<vector<int>>& grid) {
        int row = grid.size(), col = grid[0].size();//取行列数
        //初始化边界，即直接加上左（或上）的数字，因为只有这一种路径
        for(int i=1; i<row; ++i){
            grid[i][0] += grid[i-1][0];
        }
        for(int i=1; i<col; ++i){
            grid[0][i] += grid[0][i-1];
        }

        //dp中间的数，加上左和上中间大的那个数
        for(int i=1; i<row; ++i){
            for(int j=1; j<col; ++j){
                grid[i][j] += max(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[row-1][col-1];//返回右下角的值
    }
};