Screen Shot 2021-03-07 at 9.40.43 PM.png

递归

image.png

class Solution:
    def fib(self, n: int) -> int:
         if n==0:return 0
         if n==1:return 1
         return (self.fib(n-1)+self.fib(n-2))%1000000007

记忆化递归

image.png

class Solution:
    def fib(self, n: int) -> int:
        dp = [0, 1]
        for i in range(2, n + 1):
            dp.append(dp[i - 1] + dp[i - 2])
        return dp[n] % 1000000007

动态规划

image.png

image.png

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

a,b交替前进一定要横着赋值 否则a+b的值用的是更新后的a

class Solution:
    def fib(self, n: int) -> int:
        a, b, c = 0, 1, 2
        for _ in range(n):
            a,b,c = b,c,a+b+c 
        return a 

总结

1. 递归问题首先要找到动态规划的方程，并确定初始值
2. 看有几个变量交替前进
3. 根据变量设置循环