题解 | #求路径#

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    //本题为经典的动态规划问题
    //先介绍不使用空间压缩的方法
    //申请和原矩阵同样大小的dp数组
    //dp[i][j]的含义为从左上角到i，j位置的方法数一共有多少种
    //所以dp[i][j]的第一行和第一列全部都是1
    //对于一个普遍位置dp[i][j]的值也很好求
    //要么从上面来要么从左面来，所以dp[i][j]=dp[i-1][j]+dp[i][j-1]
    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;
        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];
    }
};