动态规划01-斐波那契类型一

1. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

真题点击此处：509.斐波那契数

解题方法：动态规划
思路：斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：F(n)=F(n?1)+F(n?2)

由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。
以下为代码实现：

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

其实我们也可以不用特判当n<2的情况，我们可以思考一下，斐波那契的数列为0,1,1,2,3,5……，我们不妨就用两个变量p，q分别为0,1，然后对于第n个数来说，我们循环n-1次，然后里面分别将p,q赋值为q,p+q。最后返回p就好了，以下为代码实现：

class Solution:
    def fib(self, n: int) -> int:
        p,q=0,1
        for i in range(n):
            p,q=q,p+q
        return p

时间复杂度：O（n），只进行了一次循环遍历。
空间复杂度：O（1），只使用了常量级的额外空间。

2. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

真题点击此处：70.爬楼梯

解题方法：动态规划
思路：这题的思路跟上题的斐波那契数列的思路是一样的，都能得到以下递推关系：F(n)=F(n?1)+F(n?2)，唯一的不同就是关于边界值的问题，斐波那契的前两个数的值是0,1，而爬楼梯的前两个数的值是1,2。所以实现方法也是和斐波那契数列非常相似的。

以下为代码实现：

class Solution:
    def climbStairs(self, n: int) -> int:
        p,q,r=0,0,1
        for i in range(n):
            p=q
            q=r
            r=p+q
        return r

以下为跟上题斐波那契数列第二种解法类似的代码。具体解释就不再说了，思想都是一样的。

class Solution:
    def climbStairs(self, n: int) -> int:
        p,q=0,1
        for i in range(n):
            p,q=q,p+q
        return q

时间复杂度：O（n），只进行了一次循环遍历。
空间复杂度：O（1），只使用了常量级的额外空间。

3. 第n个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

真题点击此处：1137.第n个泰波那契数

解题方法：动态规划
思路：这题跟斐波那契数列的解法是很像的，只不过一个是前两个数相加，一个是前三个数相加而已。具体思路为：
泰波那契数的边界条件是 T(0)=0,T(1)=1,T(2)=1。当 n>2时，每一项的和都等于前三项的和，因此有如下递推关系：

T(n)=T(n-1)+T(n-2)+T(n-3)

由于泰波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 T(0)、T(1) 和 T(2)。

以下为代码实现：

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
          return 0

        if n <= 2:
          return 1

        p, q, r = 0, 1, 1
        for i in range(3, n+1):
          s = p + q + r
          p, q, r = q, r, s

        return s 

同样的，我们还是可以不用特判当n<=2的时候的情况，以下为代码实现：

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

时间复杂度：O（n），只进行了一次循环遍历。
空间复杂度：O（1），只使用了常量级的额外空间。