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

不同路径的数目(一)

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];
}

全部评论

相关推荐

这是什么操作什么意思,这公司我服了...
斯派克spark:意思是有比你更便宜的牛马了
点赞 评论 收藏
分享
07-03 16:02
门头沟学院 Java
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
07-01 13:37
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务