剑指offer 48- 礼物的最大价值

在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

m,n>0

样例：

输入：
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

分析：
（1）状态表示：dp[i][j]从[0,0]到[i,j]能拿到礼物的最大价值
（2）状态如何计算
dp[i][j] = dp[i][j] + max(dp[i-1][j],dp[i][j-1]);
（3）边界问题：
dp[i][0] = dp[0][j] = 0;
return dp[n][m]
时间复杂度优化

空间复杂度

class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));//多开一个，避免边界判断
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                //这里i和j从1开始，则grid应该向左偏移一个
                dp[i][j] = grid[i-1][j-1] + max(dp[i][j-1], dp[i-1][j]);
        return dp[n][m];
    }
};

空间复杂度优化

输入数据已经给了一个数组，我们是否要再开一个数组呢？

我们可以发现，在每次转移中，grid[i][j]
总共只用了一次，也就是说在更新 dp[i][j] 后 grid[i][j]就没用了。
所以我们可以直接用grid
数组作为我们储存dp状态的数组，那么我们就不用去在开一个 dp 数组了。

class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(i && j) grid[i][j] = grid[i][j] + max(grid[i][j-1], grid[i-1][j]);
                else if(i) grid[i][j] = grid[i][j] + grid[i-1][j];
                else if(j) grid[i][j] = grid[i][j] + grid[i][j-1];
        return grid[n-1][m-1];
    }
};