Leecode-062-Unique Paths

思路：动态规划

题目描述

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

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

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

• 注意（这里有个坑，m是列数,n才是行数）

Solution：动态规划

• 确定状态方程

  • 使用一个二维数组 dp 来存储答案，dp[i][j]的值是从起始点（也就是(0,0)）走到(i, j)的路径数。

• 初始化

  • 第一行和第一列都初始化为1
  • 当 i == 0或者j==0的时候，i-1和j-1会越界

• 状态转移

  • 假设我们全都知道dp[i][j]的值，题目中说到，小机器人只能往右或者往下，那么dp[i][j]的值就是第 i 行第 j 列这个格子的上面那个格子的值加上左边那个格子的值(本质也就是杨辉三角)
  • 也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为这两个格子都可以走到dp[i][j]这个格子，那么他们的路径数之和就是dp[i][j]的值。

Java

Solution :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution{
    public int uniquePaths(int m,int n){
        // 初始化
        int[][] dp = new int[m][n];
        for (int i = 0;i < n; i++){
            dp[0][i] = 1;
        }

        for (int i = 0; i < m; i++) {
            dp[i][0] = 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];
    }
}

复杂度分析

• 时间复杂度: O(m∗n)

• 空间复杂度：O(m∗n)

方法二 ： 组合数学

• 从左上角到右下角的过程中，我们需要移动 m+n-2次，其中有 m-1 次向下移动，n-1次向右移动。

• 因此路径的总数,就等于从 m + n - 2 次移动中选择 m - 1 次向下移动的方案数量，即组合数：

因此我们直接计算出这个组合数即可。计算的方法有很多种：

1. 如果使用的语言有组合数计算的 API，我们可以调用 API 计算；
2. 如果没有相应的 API，我们可以使用

Python:

1
2
3

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

Java

1
2
3
4
5
6
7
8
9

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

复杂度分析

• 时间复杂度 ： O(m) 循环次数 y < m
• 空间复杂度： O（1）