Algorithm-LeetCode/Solutions/0062.Unique_Paths.py at main · ling67/Algorithm-LeetCode · GitHub

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.


Example 1:
Input: m = 3, n = 7
Output: 28

Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
time complexity: O(m*n)
*/

"""
1.确定状态 dp[i][j] 从[0][0]到[i][j]的路径
2.求dp[m-1][n-1]
3.初始化 dp[0][0]=1 dp[i][0]=1 dp[0][j]=1
4.递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
"""
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]   #注意二维数组初始化
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:    ## 初始条件：只有一种方法走到行为0或者列为0的地方，因为不能往左走也不能往上走
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

"""
滚动数组优化
"""
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(2)]
        dp[0][0], dp[1][0] = 1, 1
        for j in range(n):
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i%2][j] = dp[(i-1)%2][j] + dp[i%2][j-1]
        return max(dp[0][n-1], dp[1][n-1])


//1.状态定义 dp[i][j] 代表从（0，0）出发到（i,j）总共的路径数
//2.求dp[m-1][n-1]
//3.初始化 dp[0][0] = 1, dp[i][0]=1, dp[0][j]=1;
//4.递推公式 dp[i][j] = dp[i][j-1] + dp[i-1][j];
class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];

        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}