【动态规划】64. 最小路径和

64. 最小路径和

自顶向下-动态规划解法

• 每次走一步，路径和都会发生变化，那么变化的就是状态也就是路径和
• 我们定义dp[i][j]为走到(i,j)位置的最小路径和
• 那么首先base case 就是i = 0 j = 0的位置直接返回grid[0][0]
• 然后还需要判断是否越界
• 定义一个备忘录 记录子问题的解 初始化全部为-1
• 然后再dp的过程中首先判断这个子问题能不能再备忘录中查找到
• 然后计算下一步

class Solution {
    // 制作备忘录
    int[][] mem;

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 初始化 mem
        mem = new int[m][n];

        // 初始化值全部为-1
        for(int [] row:mem){
            Arrays.fill(row,-1);
        }


        // 从左上角位置0 0 走到 m - 1 n - 1
        return dp(grid,m - 1,n - 1);
    }

    int dp(int[][] grid, int i,int j){
        // base case
        if(i == 0 && j == 0){
            return grid[0][0];
        }

        // 如果索引出界  返回一个比较大的值

        // 保证在取Min的时候不会被去到
        if(i < 0 || j < 0){
            return Integer.MAX_VALUE;
        }

        // 判断当前子问题有没有解决过  如果有的话 直接返回
        if(mem[i][j] != -1){
            return mem[i][j];// 不是 -1  说明已经解决过
        }

        // 从左边或者上边开始寻找 找到他们的最小路径和 然后加上grid[i][j]
        mem[i][j] = Math.min(dp(grid,i - 1,j),dp(grid,i,j - 1)) + grid[i][j];
        return Math.min(dp(grid,i - 1,j),dp(grid,i,j - 1)) + grid[i][j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

自底向上进行递归

• base case dp[0][0] = grid[0][0];
• 另外对于第一行和第一列元素进行初始化
• 之后遍历 状态转移 自底向上

class Solution {
    public int minPathSum(int[][] grid) {
        // 自底向上的代码
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];

        // base case
        dp[0][0] = grid[0][0];

        // 第一行的所有元素都来源左边的元素 不可能来自上面
        for(int j = 1; j < n; j++){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 第一列的所有元素全部来源上面的一个元素 不可能来自于左边
        for(int i = 1; i < m; i++){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // 状态转移
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32