题目

image.png

思路

  • 思路一：暴力递归，首先定义recur(grid, i, j)表示从(0,0)到(i,j)的礼物的最大值，因此，想要求(i,j)的最大价值，我们只需求出Math.max((i-1,j), (i, j - 1)，因此递归分支为两个，我们知道(0,0)->(0,0)的礼物的最大价值就是gird[0][0]，因此这个就是终止条件。
  • 思路二：备忘录
  • 思路三：动态规划，就是递归的逆过程，定义dp[i][j]表示(0,0)到(i,j)的最大礼物价值，转移方程:dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j]

  • 思路四：优化dp数组的动态规划，画图解决

    代码

    1.    //1.暴力递归
    2.   public int maxValue(int[][] grid) {
    3.       return recur(grid, grid.length - 1, grid[0].length - 1);
    4.   }
    6.   public int recur(int[][] grid ,int i, int j) {
    7.       if (i == 0 && j == 0) return grid[0][0];
    8.       if (i < 0 || j < 0) return -1;
    9.       int value1 = recur(grid, i, j - 1);
    10.       int value2 = recur(grid, i - 1, j);
    11.       return  value1 == -1 && value2 == -1 ? -1 : Math.max(value1, value2) + grid[i][j];
    12.   }
    14.   //2. 备忘录
    15.   int[][] dp;
    16.   public int maxValue(int[][] grid) {
    17.       dp = new int[grid.length][grid[0].length];
    18.       return recur(grid, grid.length - 1, grid[0].length - 1);
    19.   }
    21.   public int recur(int[][] grid ,int i, int j) {
    22.       if (i == 0 && j == 0) return grid[0][0];
    23.       if (i < 0 || j < 0) return -1;
    24.       if (dp[i][j] != 0) return dp[i][j];
    25.       int value1 = recur(grid, i, j - 1);
    26.       int value2 = recur(grid, i - 1, j);
    27.       dp[i][j] = value1 == -1 && value2 == -1 ? -1 : Math.max(value1, value2) + grid[i][j];
    28.       return dp[i][j];
    29.   }
    31.   //3.动态规划
    32.   public int maxValue(int[][] grid) {
    33.       //表示从(0,0)到(i,j)获得礼物的最大
    34.       int[][] dp = new int[grid.length][grid[0].length];
    35.       dp[0][0] = grid[0][0];
    36.       for (int i = 1; i < grid.length; i++) {
    37.           dp[i][0] += dp[i - 1][0] + grid[i][0];
    38.       }
    39.       for (int j = 1; j < grid[0].length; j++) {
    40.           dp[0][j] += dp[0][j - 1] + grid[0][j];
    41.       }
    42.       for (int i = 1; i < grid.length; i++) {
    43.           for (int j = 1; j < grid[0].length; j++) {
    44.               dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    45.           }
    46.       }
    47.       return dp[grid.length - 1][grid[0].length - 1];
    48.   }
    50.   //4.优化dp数组动态规划，由于每次只用到前一行和前一个，所以可以优化为一维dp数组
    51.   public int maxValue(int[][] grid) {
    52.        //表示从(0,0)到(i,j)获得礼物的最大
    53.       int[] dp = new int[grid[0].length];
    54.       dp[0] = grid[0][0];
    55.       for (int j = 1; j < grid[0].length; j++) {
    56.           dp[j] += dp[j - 1] + grid[0][j];
    57.       }
    58.       for (int i = 1; i < grid.length; i++) {
    59.           dp[0] += grid[i][0];
    60.           for (int j = 1; j < grid[0].length; j++) {
    61.               dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i][j];
    62.           }
    63.       }
    64.       return dp[grid[0].length - 1];
    65.   }

    礼物的最大价值