LeetCode

Leetcode 62,63- 不同路径

动态规划,水题

Posted by 刘知安 on 2019-11-07
文章目录
  1. Leetcode 62,63- 不同路径
    1. 1. 题目描述
    2. 2. 思路
    3. 3. 代码
  2. 4.同类题

Leetcode 62,63- 不同路径

1. 题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

1
2
3
4
5
6
7
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

2. 思路

一看就是动态规划，列举一下，具体的前后关系就有了：

也就是每个位置的路径数等于它上面和左边位置路径数之和。

有个坑点就是，我最开始以为假如m=1,n=1时算0种情况，其实算1种。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 动态规划
public int uniquePaths(int m, int n) {
    int[][] res = new int[m][n];

    // 初始值
    res[0][0] = 1;   // 坑点，只有1个格子也算一种情况
    for (int r = 1; r < m; r++) res[r][0] = 1;
    for (int c = 1; c < n; c++) res[0][c] = 1;

    // 每个值等于它的上面的值和左边的值之和
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            res[i][j] = res[i - 1][j] + res[i][j - 1];
        }
    }

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

4.同类题

  • LeetCode 63- 不同路径②

就是加了一个限制，即棋盘上可能有障碍物。

其实思路和之前类似，只不过障碍物处的可能路径数为0。注意一下边界初始化的特殊情况就行啦，同样也是上面加左边位置可能的路径数之和。代码如下：

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
// 动态规划  63题
   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
       int m = obstacleGrid.length;
       int n = obstacleGrid[0].length;
       int[][] res = new int[m][n];

       // 如果第一个棋子就是障碍物，怎么都走不动，返回0
       if (obstacleGrid[0][0] == 1) return 0;

       // 初始值
       res[0][0] = 1;
       // 在第一行和第一列，
       for (int r = 1; r < m; r++) {
           // 如果当前有障碍，置0
           if (obstacleGrid[r][0] == 1)
               res[r][0] = 0;
               // 否则置为它的前一个位置的路径数
           else
               res[r][0] = res[r - 1][0];
       }
       for (int c = 1; c < n; c++) {
           if (obstacleGrid[0][c] == 1)
               res[0][c] = 0;
           else
               res[0][c] = res[0][c - 1];
       }

       // 每个值等于它的上面的值和左边的值之和
       for (int i = 1; i < m; i++) {
           for (int j = 1; j < n; j++) {
               if (obstacleGrid[i][j] == 1)
                   res[i][j] = 0;
               else
                   res[i][j] = res[i - 1][j] + res[i][j - 1];
           }
       }

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

FEATURED TAGS
LeetCode
FRIENDS