leetcode动态规划(一)509+1137

1.509斐波那契数-简单

1）状态转移方程

F(n)=F(n−1)+F(n−2)

2）边界条件

F(0)=0，F(1)=1

3）复杂度

时间复杂度：O(n)

空间复杂度：O(1)

2.1137第N个泰波那契数-简单

1）状态转移方程

Tn+3 = Tn + Tn+1 + Tn+2(n>=0)

2）边界条件

T0 = 0, T1 = 1, T2 = 1

3）复杂度

时间复杂度：O(n)

空间复杂度：O(1)

4)python代码

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        p, q, r, s = 0, 1, 1, 2
        for i in range(3, n):
            p, q, r = q, r, s
            s = p + q + r
        return s

3.参考资料​​​​​​​ 

力扣​​​​​​​

力扣