JZ47 礼物的最大价值

描述
在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输入这样的一个二维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12

错误解法：贪心算法

每一次选择，要么向右，要么向下，总是可以找到当前的最优解。

贪心算法并不能保证总是最优解。局部最优不能保证全局最优。对于有确定答案的题，贪心算法并不能保证通过所有case。

public int maxValue (int[][] grid) {
   int sum = grid[0][0];
   int i = 0, j = 0;
   while (i < grid.length && j < grid[0].length ) {
       int x = 0, y = 0;
       if (i + 1 <  grid.length && j < grid[0].length ) {
           x = grid[i + 1][j];
       }
       if (i < grid.length && j + 1 < grid[0].length) {
           y = grid[i][j + 1];
       }
       if (x > y) {
           i++;
           sum += x;
       } else {
           j++;
           sum += y;
       }
   }
   return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

对于不确定的人生而言，不能回溯，也不可动态规划，贪心算法或许是最佳的选择。

解法一：动态规划

因为后面的值依赖于前面的值，可以考虑动态规划

用原来的数组来存储中间值，节省存储空间。

第一行的值只能来源于第一行，所以累加即可。第一列的值只能来源于第一列，同理累加即可。

然后从[1,1]位置遍历数组，对于每个元素添加来自上方或者左方的较大值。最终返回数组右下角元素即可。

public int maxValue (int[][] grid) {
   int m=grid.length;
   int n = grid[0].length;
   for(int i=1;i<n;i++){
       grid[0][i]+=grid[0][i-1];
   }
   for(int j=1;j<m;j++){
       grid[j][0]+=grid[j-1][0];
   }
   for(int i=1;i<m;i++){
      for(int j=1;j<n;j++){
          grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
      }
   }
   return grid[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法二：递归

从右下角开始递归，递归出口为[0,0]。对于上边界y=0和左边界x=0特殊处理。

每个元素添加来自上方或者左方的较大值。最终返回数组右下角元素即可。

dp[m][n]=grid[m][n]+Math.max(recursion(grid,dp,m,n-1),recursion(grid,dp,m-1,n));
1

public int maxValue (int[][] grid) {
   int m= grid.length;
   int n = grid[0].length;
   int[][] dp = new int[m][n];
   return recursion(grid,dp,m-1,n-1);
}

private int recursion(int[][] grid, int[][] dp,int m,int n){
   if(m==0&&n==0){
       dp[0][0]=grid[0][0];
       return dp[0][0];
   }
   if(m==0){
       dp[0][n]=grid[0][n]+recursion(grid,dp,0,n-1);
   }
   if(n==0){
       dp[m][0]=grid[m][0]+recursion(grid,dp,m-1,0);
   }
   if(dp[m][n]==0){
       dp[m][n]=grid[m][n]+Math.max(recursion(grid,dp,m,n-1),recursion(grid,dp,m-1,n));
   }
   return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

涉及数据结构：数组
涉及算法：动态规划、递归