题解 | #求路径#

题解一： 动态规划
题解思路： dp[i][j]代表从起点到(i,j)的路径数量,到(i,j)只能从(i-1,j)和(i,j-1)到达。所以dp[i][j] = dp[i-1][j]+dp[i][j-1];
图示：54 dp数组变化

*复杂度分析：**
时间复杂度：O(MN)
空间复杂度：O(MN)
实现如下：

class Solution {
public:
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        int dp[m][n];
        //初始化
        for(int i = 0;i<n;i++) dp[0][i] = 1; 
        for(int i = 0;i<m;i++) dp[i][0] = 1;
        //dp数组的构建
        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];
    }
};

题解二： 记忆化+dfs
题解思路：普通递归由于太多的重复计算，所以普通递归最终会超时。 使用记忆化记录之前的计算，
重复计算。
复杂度分析：
时间复杂度：O(MN)
空间复杂度：O(MN)
实现如下：

class Solution {
public:
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    vector<vector<int> >ans; //用于记录之前计算过的位置
    int reco_dfs(int x,int y,int n,int m){
        if(x==m-1||y==n-1) return 1;
        if(ans[x][y]) return ans[x][y];   //如果x,y之前计算过，那么直接返回
        ans[x][y] = reco_dfs(x+1, y,n,m)+reco_dfs(x, y+1,n,m);
        return ans[x][y];
    }
    int uniquePaths(int m,int n){
       ans = vector<vector<int>>(m,vector<int>(n,0));
       return reco_dfs(0,0,n,m);  
    }
};