搜索

今天重新看了下动态规划,
它和递归的区别就是,它是自下而上的。
还了解到状态压缩

如果我们发现每次状态转移只需要 DP table 中的一部分,那么可以尝试用状态压缩来缩小 DP table 的大小,只记录必要的数据
于是就刷了这道简答题,用到了状态压缩
class Solution:
    def fib(self, n: int) -> int:
            if n == 0:
                return 0
            if n == 1 or n == 2:
                return 1
            prev = 1
            curr = 1
            for i in range(3, n + 1):
                sum = prev + curr
                prev = curr
                curr = sum
            return sum

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
5
查看目录

目录

来自 《leetcode 509 斐波那契数》
评论

染念

有你的生活真好~