算法训练Day39|62.不同路径 ● 63. 不同路径 II

 1class Solution {
 2    public int uniquePaths(int m, int n) {
 3        // 二维数组
 4        int[][] dp = new int[m][n];
 5
 6        // dp[m][n]:到达m,n位置，有dp[m][n]种路径
 7        // 初始化
 8        for (int i = 0; i < m; i++) {
 9            dp[i][0] = 1;
10        }
11        for (int i = 0; i < n; i++) {
12            dp[0][i] = 1;
13        }
14        for (int i = 1; i < m; i++) {
15            for (int j = 1; j < n; j++) {
16                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17            }
18        }
19        return dp[m - 1][n - 1];
20    }
21}
22

 1class Solution {
 2    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3        // 求出总路径数 - 障碍位置路径数？
 4
 5        int m = obstacleGrid.length; // 获取行数
 6        int n = obstacleGrid[0].length; // 获取列数
 7        // dp[m][n] 表示节点（m,n）处潜在路径数
 8        int[][] dp = new int[m][n];
 9        // 当起始节点和终止节点均有障碍时，无结果，直接返回0
10        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
11            return 0;
12        }
13        // 每行的首位数字初始化(也即首列初始化)，遇到障碍设置为0
14        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
15            dp[i][0] = 1;
16        }
17        // 每列的首位数字初始化(也即首行初始化)，遇到障碍设置为0
18        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
19            dp[0][j] = 1;
20        }
21        // 遍历输出dp[][]数组值
22        for (int i = 1; i < m; i++) {
23            for (int j = 1; j < n; j++) [
24                if (obstacleGrid[i][j] == 0) { // 当前节点没有障碍时，正常执行
25                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
26                } else {
27                    dp[i][j] = 0; // 有障碍时直接赋值为0
28                }
29            ]
30        }
31        // 数组下标从0 开始，m - 1, n - 1也就代表（m,n）位置
32        return dp[m - 1][n - 1];
33
34    }
35}
36