第一种方法 DFS 果然超时

class Solution {
public:
    int count = 0;
    int uniquePaths(int m, int n) {
        vector<vector<bool>> visited(m, vector<bool>(n,false));
        path(visited,m,n,0,0);
        return count;
    }
    void path(vector<vector<bool>> visited, int m, int n, int i, int j){
        if(i<0||i>=m||j<0||j>=n||visited[i][j])
            return;
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        visited[i][j] = true;
        path(visited,m,n,i,j+1);
        path(visited,m,n,i+1,j);
        visited[i][j] = false;  // 复原
    }


};

第二种方法 动态数组，同动态数组这题则和跳楼梯类似，每次只能跳一个或者两个台阶，跳到n阶有多少种跳法

class Solution {
public:
    int count = 0;
    int uniquePaths(int m, int n) {

        // 如果全部直接初始化为1，省掉了定义basecase这部
        vector<vector<int>> dp(m, vector<int>(n,1));

        // dp数组含义，从左上角到i，j一共有多少种不同路径。
        // //basecase
        // for (int i = 0; i < m; ++i) {
        //     dp[i][0] = 1;   // 左上角到dp[i][0]显然只有一条路径
        // }
        // for (int j = 0; 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];
    }
};