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

不同路径的数目(一)

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

全部评论

相关推荐

找到实习了&nbsp;给了150一天&nbsp;但是说是低代码&nbsp;值得去吗
码农索隆:是在没实习,可去,待个一两周,不行就润呗
点赞 评论 收藏
分享
哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
05-19 15:21
已编辑
门头沟学院 Java
白火同学:你才沟通了200,说实话,北上广深杭这里面你连一座城市的互联网公司都没投满呢,更别说还有各种准一线二线城市了。等你沟通突破了三位数,还没结果再考虑转行的事吧。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:20
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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