62.不同路径

文章：6. 不同路径

题目：62. 不同路径

【思路】

动态规划五部曲：

1.确定dp数组以其下标含义

dp[i] [j]：表示从（0,0）出发，到(i,j)有dp[i] [j]条路径

2.确定递推公式

dp[i] [j]只能从两个方向推导：dp[i-1] [j]/dp[i] [j-1]

因此：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

3.数组初始化

dp[0] [0] = 0

dp[1] [0] = 1

dp[0] [1] = 1

4.确定遍历顺序

从上到下，从左到右

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0 ; i < m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0 ; i < n ; i++){
            dp[0][i] = 1;
        }
        for(int i = 1;i < m;i++){
            for(int j = 1; j < n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
    dp:=make([][]int,m+1)
    for i := range dp{
        dp[i] = make([]int,n+1)
        dp[i][0] = 1
    }
    for i:=0;i<n;i++{
        dp[0][i] = 1
    }
    
    for i :=1;i<m;i++{
        for j := 1 ;j < n;j++{
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    } 
    return dp[m-1][n-1]

}

63.不同路径II

文章：7. 不同路径II

题目：63. 不同路径 II

【思路】

1.确定dp数组及其下标

dp[i] [j] : 从（0,0）出发，到(i,j)有dp[i] [j]条不同路径

2.确定递归公式

dp[i] [j] 可以从dp[i-1] [j] 和 dp[i] [j-1]得到，但是要注意是在没有障碍的前提下。

if(障碍==0)dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

3.数组初始化

需要初始化的是最左和最上的边界，初始化为1

但本题有个约束：障碍物及其后的均为0，一旦遇到了障碍物停止数组的初始化赋值操作。

4.确定遍历顺序

从左到右从上到下

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][]dp = new int[m][n];
        for(int i = 0 ; i < m && obstacleGrid[i][0] != 1 ; i++)dp[i][0] = 1;
        for(int i = 0 ; i < n && obstacleGrid[0][i] != 1 ; i++)dp[0][i] = 1;
        for(int i = 1;i<m;i++){
            for(int j = 1;j < n;j++){
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([][]int,m)
    for i := range dp{
        dp[i] = make([]int,n)
        if obstacleGrid[i][0] != 1{
            dp[i][0] = 1
        }
    }
    for i:=0;i < n;i++{
        if obstacleGrid[0][i] ==0{
            dp[0][i] = 1
        }
    }
    for i :=1;i<m;i++{
        for j:=1;j< n;j++{
            if obstacleGrid[i][j] == 0{
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
}

【算法总结】

  • 不同路径、不同路径II：使用递归，II需要特判障碍物出现的情况，当障碍物出现在最左和最上时，障碍物之后的路径不需要初始化！

【语言总结】

  • Go：初始化二维数组需要：
1
2
3
4
dp := make([][]int,m)
    for i := range dp{
        dp[i] = make([]int,n)
    }