题目

image.png

思路

  • 和不同路径差不多，不多说

    代码

    1.   //1.暴力递归
    2.   public int minPathSum(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[i][j];
    8.       if (i < 0 || j < 0) return Integer.MAX_VALUE;
    9.       return Math.min(recur(grid, i - 1, j), recur(grid, i, j - 1)) + grid[i][j];
    10.   }
    12.   //2.备忘录
    13.   int[][] dp;
    14.   public int minPathSum(int[][] grid) {
    15.       dp = new int[grid.length][grid[0].length];
    16.       return recur(grid, grid.length - 1, grid[0].length - 1);
    17.   }
    19.   public int recur(int[][] grid, int i, int j) {
    20.       if (i == 0 && j == 0) return grid[i][j];
    21.       if (i < 0 || j < 0) return Integer.MAX_VALUE;
    22.       if (dp[i][j] != 0) return dp[i][j];
    23.       dp[i][j] =  Math.min(recur(grid, i - 1, j), recur(grid, i, j - 1)) + grid[i][j];
    24.       return dp[i][j];
    25.   }
    27.   //3.动态规划
    28.   public int minPathSum(int[][] grid) {
    29.       if (grid.length == 0) return 0;
    30.       int[][] dp = new int[grid.length][grid[0].length];
    31.       dp[0][0] = grid[0][0];
    32.       for (int i = 1; i < grid.length; i++) {
    33.           dp[i][0] += dp[i - 1][0] + grid[i][0];
    34.       }
    35.       for (int j = 1; j < grid[0].length; j++) {
    36.           dp[0][j] += dp[0][j - 1] + grid[0][j];
    37.       }
    38.       for (int i = 1; i < grid.length; i++) {
    39.           for (int j = 1; j < grid[0].length; j++) {
    40.               dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    41.           }
    42.       }
    43.       return dp[grid.length - 1][grid[0].length - 1];
    44.   }
    46.   //4.动态规划，优化dp数组
    47.   public int minPathSum(int[][] grid) {
    48.       if (grid.length == 0) return 0;
    49.       int[] dp = new int[grid[0].length];
    50.       dp[0] = grid[0][0];
    51.       for (int j = 1; j < grid[0].length; j++) {
    52.           dp[j] += dp[j - 1] + grid[0][j];
    53.       }
    54.       for (int i = 1; i < grid.length; i++) {
    55.           dp[0] += grid[i][0];
    56.           for (int j = 1; j < grid[0].length; j++) {
    57.               dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
    58.           }
    59.       }
    60.       return dp[grid[0].length - 1];
    61.   }

    最小路径和