当前位置: 首页 > >

礼物的最大价值--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>& grid) {
int m = grid[0].size();
int n = grid.size();
vectortemp(m, 0);
vector> dp(n,vector(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>& grid) {
int m = grid[0].size();
int n = grid.size();
vector 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>& 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




友情链接: