礼物的最大价值--dp的一步步优化

0x01.问题

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

0x02.简要分析

在矩阵中拿礼物，每次只能往右走或往下走。求的是所拿礼物的最大值。

这一看就是很经典的动态规划问题，当然也可以用DFS去搜索，不过效率太低了，这个题最好的办法还是dp来解决。

状态转移方程也好找，就是左边和上面里面的最大值加上自身的价值。

	 	dp[i][j] = grid[i][j];
        if (i == 0 && j != 0) dp[i][j] += dp[i][j - 1];
        if (i != 0 && j == 0) dp[i][j] += dp[i - 1][j];
        if (i != 0 && j != 0) dp[i][j] += max(dp[i][j - 1], dp[i - 1][j]);

这个问题可以不需要考虑初始条件，因为这个转移方程可以包括所所有的情况。

0x03.解决代码–二维dp

int maxValue(vector<vector<int>>& grid) {
    int m = grid[0].size();
    int n = grid.size();
    vector<int>temp(m, 0);
    vector<vector<int>> dp(n,vector<int>(m,0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = grid[i][j];
            if (i == 0 && j != 0) dp[i][j] += dp[i][j - 1];
            if (i != 0 && j == 0) dp[i][j] += dp[i - 1][j];
            if (i != 0 && j != 0) dp[i][j] += max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[n - 1][m - 1];
}

我们看一下时间复杂度：O（N^2），这个应该没话说了，这是解决这个问题的最低复杂度。

空间复杂度O（N^2），这个肯定可以优化，毕竟这个空间消耗还是太大了。

我们仔细观察一下转移方程，发现dp里面j下标的值其实只与j下标和j-1下标的值有关，所以我们可以把二维的dp优化成一维的dp，这样空间就可以大幅度缩减了。

0x04.解决代码–优化一：一维dp

int maxValue(vector<vector<int>>& grid) {
    int m = grid[0].size();
    int n = grid.size();
    vector<int> dp(m + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[j + 1] = max(dp[j], dp[j + 1]) + grid[i][j];
        }
    }
    return dp[m];
}

空间复杂度：O（N）
这个方法其实已经很好了，但是，我们还可以进一步的优化，我们发现grid数组的值只在判断的时候使用了一次，所以我们可以直接改变grid数组的值，将grid的值作为dp数组的值，再来进行二维的dp处理，这样就连dp的空间也优化掉了。

0x05.解决代码–优化二：原地修改

int maxValue(vector<vector<int>>& grid) {
    int m = grid[0].size();
    int n = grid.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j != 0) grid[i][j] += grid[i][j - 1];
            if (i != 0 && j == 0) grid[i][j] += grid[i - 1][j];
            if (i != 0 && j != 0) grid[i][j] += max(grid[i][j - 1], grid[i - 1][j]);
        }
    }
    return grid[n - 1][m - 1];
}

ATFWUS --Writing By 2020–03–28