Python教程

【Leetcode】NO.509&NO.1137 斐波那契数（Python）[动态规划]

本文主要是介绍【Leetcode】NO.509&NO.1137 斐波那契数（Python）[动态规划]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：斐波那契数

思路

动态思想的简单题，直接版本是创建一个动态数组存储；
优化版本是只保存最终的结果；空间复杂度从O(n) 减到O（1）；

代码

class Solution:
    def tribonacci(self, n: int) -> int:
        if n<2:
            return n
        if n == 2:
            return 1
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n+1):
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        return dp[n]
这篇关于【Leetcode】NO.509&NO.1137 斐波那契数（Python）[动态规划]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航