动态规划

斐波那契类型

  • 第 N 个泰波那契数

    难度：简单

    泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
    示例 1：
    输入：n = 4
    输出：4
    解释：
    T_3 = 0 + 1 + 1 = 2
    T_4 = 1 + 1 + 2 = 4

    示例 2：
    输入：n = 25
    输出：1389537

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution(object):
      def tribonacci(self, n):
          """
          :type n: int
          :rtype: int
          """
          if n == 0:
              return 0
          elif n<= 2:
              return 1
          a = 0
          b = 1
          c = 1
          for i in range (2,n):
              tem = a 
              a = b
              b = c
              c = a+b+tem
          return c

    解析
    泰波那契数的边界条件是 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)。 根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 T(n) 只和前三项有关，因此可以使用「滚动数组思想」将空间复杂度优化成 O(1)

    复杂度分析
    时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
    空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。