题解 | #求路径#

题目思路：题目两种走法，向右或者向下，则dp的值就为上面或者左边两者值的加和

解法一：打表，开二维数组求dp
正常求就行，一般对于多组输入，打表有一定优势，但此题有些不同。。

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
    int dp[105][105];
    for(int i=1; i<=100; i++) {
        dp[1][i]=1;
        dp[i][1]=1;
    }
    for(int i=2; i<=100; i++) {
        for(int j=2; j<=100; j++) {
            dp[i][j]=dp[i-1][j]+ dp[i][j-1];
        }
    }
    return dp[m][n];
    }
};

解法二：滚动数组（优化），开一维数组，省空间
dp的值只和本行和上一行有关，进而发现递推式：dp[i]=dp[i]+dp[i-1]
即dp值等于上一层dp[i]+左边dp[i-1],进一步优化

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
    int dp[105];
    for(int i=1;i<=n;i++){
        dp[i]=1;
    }
    for(int i=2;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j==1){
                dp[j]=1;
            }
            else if(j>1){
                dp[j]+=dp[j-1];
            }
        }
    }
    return dp[n];
    }
};