题解 | #不同路径的数目(一)#
不同路径的数目(一)
https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358
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];
}
