剑指offer-72、礼物的最⼤价值

题⽬描述

在⼀个m × n的棋盘的每⼀格都放有⼀个礼物，每个礼物都有⼀定的价值（价值⼤于 0）。你可以从棋盘的左上⻆开始拿格⼦⾥的礼物，并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输⼊这样的⼀个⼆维数组，

1. [
2. [1,3,1],
3. [1,5,1],
4. [4,2,1]
5. ]

复制代码

那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为 12
思路及解答

基础动态规划

这道题其实⼀看就知道是动态规划，棋盘中的每个⼩格⼦，都是和上⽅，或者左⽅的格⼦有关。既然是动态规划，那么我们先定义状态：
dp[j]表示到达(i,j)位置时能获得的最大礼物价值
状态转移：dp[j] = max(dp[i-1][j], dp[j-1]) + grid[j]

1. public int maxValue(int[][] grid) {
2.     if (grid == null || grid.length == 0 || grid[0].length == 0) {
3.         return 0;
4.     }
5.    
6.     int m = grid.length, n = grid[0].length;
7.     int[][] dp = new int[m][n];
8.    
9.     // 初始化起点
10.     dp[0][0] = grid[0][0];
11.    
12.     // 初始化第一行：只能从左边来
13.     for (int j = 1; j < n; j++) {
14.         dp[0][j] = dp[0][j-1] + grid[0][j];
15.     }
16.    
17.     // 初始化第一列：只能从上边来
18.     for (int i = 1; i < m; i++) {
19.         dp[i][0] = dp[i-1][0] + grid[i][0];
20.     }
21.    
22.     // 填充其余位置
23.     for (int i = 1; i < m; i++) {
24.         for (int j = 1; j < n; j++) {
25.             dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
26.         }
27.     }
28.    
29.     return dp[m-1][n-1];
30. }

复制代码

每个位置的计算只依赖左边和上边的结果，通过双重循环自左上向右下填充整个dp表

• 时间复杂度：O(mn)
  
• 空间复杂度：O(mn)
  

空间优化动态规划

观察发现当前行只依赖上一行，可以使用一维数组进行空间优化，利用dp[j]在更新前存储上一行第j列的值，更新后存储当前行第j列的值，实现空间复用
dp[j]表示当前行第j列的最大价值，滚动更新

1. public int maxValue(int[][] grid) {
2.     if (grid == null || grid.length == 0 || grid[0].length == 0) {
3.         return 0;
4.     }
5.    
6.     int m = grid.length, n = grid[0].length;
7.     int[] dp = new int[n];
8.    
9.     // 初始化第一行
10.     dp[0] = grid[0][0];
11.     for (int j = 1; j < n; j++) {
12.         dp[j] = dp[j-1] + grid[0][j];
13.     }
14.    
15.     // 处理后续行
16.     for (int i = 1; i < m; i++) {
17.         // 更新第一列
18.         dp[0] += grid[i][0];
19.         
20.         for (int j = 1; j < n; j++) {
21.             // dp[j]代表上一行第j列的值（从上方来）
22.             // dp[j-1]代表当前行第j-1列的值（从左边来）
23.             dp[j] = Math.max(dp[j], dp[j-1]) + grid[i][j];
24.         }
25.     }
26.    
27.     return dp[n-1];
28. }

复制代码

• 时间复杂度：O(mn)
  
• 空间复杂度：O(n)
  

原地修改动态规划（最优解）

修改原数组，直接使用grid数组作为dp表，避免额外空间分配

1. public int maxValue(int[][] grid) {
2.     if (grid == null || grid.length == 0 || grid[0].length == 0) {
3.         return 0;
4.     }
5.    
6.     int m = grid.length, n = grid[0].length;
7.    
8.     // 初始化第一行
9.     for (int j = 1; j < n; j++) {
10.         grid[0][j] += grid[0][j-1];
11.     }
12.    
13.     // 初始化第一列
14.     for (int i = 1; i < m; i++) {
15.         grid[i][0] += grid[i-1][0];
16.     }
17.    
18.     // 填充其余位置
19.     for (int i = 1; i < m; i++) {
20.         for (int j = 1; j < n; j++) {
21.             grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
22.         }
23.     }
24.    
25.     return grid[m-1][n-1];
26. }

复制代码

• 时间复杂度： O(nm) ，需要计算完⾥⾯的⼩格⼦
  
• 空间复杂度： O(1) ，优化后可以实现原地操作，不需要额外的空间
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

不错，里面软件多更新就更好了

过来提前占个楼

分享、互助 让互联网精神温暖你我

分享、互助 让互联网精神温暖你我

热心回复！

谢谢分享，辛苦了

谢谢分享，试用一下

东西不错很实用谢谢分享

东西不错很实用谢谢分享

喜欢鼓捣这些软件，现在用得少，谢谢分享！