leetcode解题: Unique Paths (62)

发表于 | 分类于

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.

解法1：DP O(N^2) with O(N^2) 空间

很直接的2维dp问题，对于任意一个点i,j,到达它的办法可以从上面过来，也可以从左面过来。
所以总的办法数是dp[i][j] = dp[i - ][j] + dp[i][j -1]
结果就是dp[m - 1][n - 1]

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    int[][] dp = new int[m][n];
    
    for (int j = 0; j < n; j++) {
        dp[0][j] = 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];
}

解法2：DP O(N^2) with O(N) 空间

和triangle相类似的思路，dp的过程是自上而下自左而右，那么可以用滚动数组来减少内存的使用。

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) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    int[] dp = new int[n];  
    for (int j = 0; j < n; j++) {
        dp[j] = 1;
    }
        
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1]; // dp[j] initially stores the previous row's calculation
        }
    }
    
    return dp[n - 1];
}