1. 礼物最大价值

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

  1. 示例 1:
  3. 输入: 
  4. [
  5.   [1,3,1],
  6.   [1,5,1],
  7.   [4,2,1]
  8. ]
  9. 输出: 12
  10. 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
  13. 提示：
  15. 0 < grid.length <= 200
  16. 0 < grid[0].length <= 200

思路：

  • 从[0][0]位置开始探索；
  • 判断当前位置左边的数与下面的数的大小，前提是昨天左边的数和下边的数不越界；
  • 选择大的数，进行递归，直到到达最后一个数grid[grid.length()-1][grid[0].length-1]；
  • 每次递归过程中需要记录记录路径总长度；
class Solution {
    public int maxValue(int[][] grid) {
        int res = grid[0][0];
        return operate(grid,0,0,res);
    }

    public int operate(int[][] grid,int i,int j,int total){
        // 到达最后一位
        if(i==grid.length-1 && j == grid[0].length-1){
            return total;
        }
        int down = 0;
        int right = 0;
        // 向右
        if(j+1>=grid[0].length){
            right = Integer.MIN_VALUE;
        }else{
            right = grid[i][j+1];
        }
        // 向下
        if(i+1>=grid.length){
            down = Integer.MIN_VALUE;
        }else{
            down = grid[i+1][j];
        }
        if(right>down){
            total+=right;
            return operate(grid,i,j+1,total);
        }else{
            total+=down;
            return operate(grid,i+1,j,total);
        }

    }
}
  • 上述方法错误的原因：
    • 单单考虑到每一步都是最优，就认为是全局最优了；

但是如果输入[[1,2,5],[3,2,1]]，这样以每一步都最优，就会漏掉最大的5，造成最终结果不是最优解。

  • 动态规划

    class Solution {
  public int maxValue(int[][] grid) {
      int m = grid.length; // 行
      int n = grid[0].length; // 列
      for(int i=0;i<m;i++){
          for(int j=0;j<n;j++){
              if(i==0&&j==0) continue;
              if(i==0){
                  grid[i][j] += grid[i][j-1];
              }else if(j==0){
                  grid[i][j] += grid[i-1][j];
              }else {
                  grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
              }
          }
      }
      return grid[m-1][n-1];
  }
}

    思路：

  • 设 f(i, j)为从棋盘左上角走至单元格 (i ,j)的礼物最大累计价值，易得到以下递推关系：f(i,j) 等于 f(i,j-1) 和 f(i-1,j) 中的较大值加上当前单元格礼物价值 grid(i,j)。

    动态规划：

  • 状态定义：设动态规划矩阵 dp ，dp(i,j) 代表从棋盘的左上角开始，到达单元格 (i,j) 时能拿到礼物的最大累计价值。

  • 转义方程：

image.png