LeetCode 62. Unique Paths

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int r = 0; r < m; ++r)
            dp[r][0] = 1;
        for (int c = 0; c < n; ++c)
            dp[0][c] = 1;
        for (int r = 1; r < m; ++r)
            for (int c = 1; c < n; ++c)
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        return dp[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int uniquePaths(int m, int n) {
        int c = min(m, n);
        vector<int> dp(c, 1);
        for (int i = 1; i < max(m, n); ++i)
            for (int j = 1; j < c; ++j)
                dp[j] += dp[j - 1];
        return dp[c - 1];
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int x = m, y = 1; y < n; ++x, ++y)
            ans = ans * x / y;
        return ans;
    }
};
1
2
3
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)