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?
    62. Unique Paths - 图1
    Above is a 7 x 3 grid. How many possible unique paths are there?

    Example 1:
    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 -> Right -> Down
    2. Right -> Down -> Right
    3. Down -> Right -> Right
    Example 2:
    Input: m = 7, n = 3
    Output: 28

    Constraints:

    • 1 <= m, n <= 100
    • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
    Memory Usage: 6.5 MB, less than 100.00% of C++ online submissions for Unique Paths.

    1. class Solution {
    2. public:
    3.     int uniquePaths(int m, int n) {
    4.         if (m == 1 || n == 1) {
    5.             return 1;
    6.         }
    7.         vector<vector<int>> dp(m, vector<int>(n, 1));
    8.         for (int i = 1; i < m; i++) {
    9.             for (int j = 1; j < n; j++) {
    10.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    11.             }
    12.         }
    13.         return dp[m - 1][n - 1];
    14.     }
    15. };

    Runtime: 4 ms, faster than 8.87% of C++ online submissions for Unique Paths.
    Memory Usage: 6 MB, less than 100.00% of C++ online submissions for Unique Paths.

    1. class Solution {
    2. public:
    3.     int uniquePaths(int m, int n) {
    4.         vector<int> pre(n, 1);
    5.         vector<int> cur(n, 1);
    6.         for (int i = 1; i < m; i++) {
    7.             for (int j = 1; j < n; j++) {
    8.                 cur[j] = pre[j] + cur[j - 1];
    9.             }
    10.             swap(cur, pre);
    11.         }
    12.         return pre[n - 1];
    13.     }
    14. };

    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
    Memory Usage: 6.1 MB, less than 100.00% of C++ online submissions for Unique Paths.

    class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> cur(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }
};