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

https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358

class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        if m == 1 or n == 1:
            return 1
        a = [1]*n
        for i in range(m-1):
            for j in range(2,n+1):
                
                a[j-1] = a[j-1] + a[j-2]
        return a[n-1]
可以把空间复杂度缩减到O(min(n,m)),例如当n比m小时,第一行为全1,第二行算出来的值直接覆盖第一行,因为算第三行时用不到第一行,所以当第一轮循环结束a[i]是第二行的第i个值。
当m较小时就竖着算,从第一列到最后一列。时间复杂度还是O(mn)
原始一点点的解法 文章被收录于专栏

尽量不借助面向对象的思想,自己去实习具体过程

全部评论

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
07-08 13:48
门头沟学院 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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