题解 | #不同路径的数目(一)#

dp[i][j] 表示到达（i,j）有多少中方法。
从最后一个状态出发，dp[i][j] = dp[i-1][j] + dp[i][j-1]，表示达到最后一个点的方法由 走到(i-1,j)的方法 和 走到(i,j-1)的方法相加。
注意限制条件，当i=0时，只能从当前点的上方下来，当j=0时，只能从当前点左边过来。
观察转移方程选择dp表填充方式
int uniquePaths(int m, int n ) 
{
    // write code here
    int dp[m][n];
    memset( dp,0,sizeof(dp) );
    
    dp[0][0] = 1;
    
    for( int j = 0;j < n;++j )
    {
        for( int i = 0; i < m;++i )
        {
            if( !i && j ) dp[i][j] = dp[i][j-1];
            else if( i && !j ) dp[i][j] = dp[i-1][j];
            else if( i && j ) dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}