LeetCode第62题（动态规划）：不同路径

LeetCode第62题（动态规划）：不同路径

========================

题目如下：

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
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

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

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

 

示例 1：


输入：m = 3, n = 7
输出：28
示例 2：

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

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6
 

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

我的代码

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
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        //dp[0][0] = 1;
        for(int i=0;i<n;i++) {
            dp[0][i] = 1;
        }
        for(int i=1;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];
                //cout<< i <<"  "<< j <<"  "<<dp[i-1][j]<<" "<<dp[i][j-1]<<"  "<<dp[i][j]<<endl;
            }
        }
//        for(int i=0;i<m;i++){
//            for(int j=0;j<n;j++){
//                //cout<< i <<"  "<< j <<"  "<<dp[i-1][j]<<" "<<dp[i][j-1]<<"  "<<dp[i][j]<<endl;
//            }
//        }
        //cout << dp[m-1][n-1];
        return dp[m-1][n-1];
    }
};

复杂度分析

  • 时间复杂度：O(mn)。
  • 空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到 f(i, j)仅与第 i 行和第 i-1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。

心得： 这是一道比较经典的动规题，难度偏简单，主要是找到dp[i][j] = dp[i-1][j] + dp[i][j-1]这样一个关系，那么问题便能迎刃而解。我的解法用了双循环，应该是可以进一步优化的，虽然代码AC了，但还未达到最优时间复杂度。

官方方法二：组合数学

思路与算法

C++代码
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return ans;
    }
};
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;
    }
}
Python3代码
1
2
3
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

复杂度分析

  • 时间复杂度：O(min(m,n))。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。

  • 空间复杂度：O(1)。

心得： 官方这种解法就离谱，，，，，用Python简直就是秒解。
题目链接：https://leetcode-cn.com/problems/unique-paths/