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.

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

当前走法等于上边和左边格子之和
花花酱： https://www.youtube.com/watch?v=fmpP5Ll0Azc
????王：https://www.youtube.com/watch?v=O9GhDaafmmo

方法1: DP

code

易错点：

1. 如果没有continue那句特判的话，会覆盖掉myTable[1][1] = 1 的赋值而导致所有值为0
2. 注意循环从i = 1, j = 1开始，因为需要访问[i - 1], [j - 1]

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

方法2: memoize

code