动态规划

斐波那契类型

  • 斐波那契数列

    难度：简单

    斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。
    示例 1：
    输入：n = 2
    输出：1
    解释：F(2) = F(1) + F(0) = 1 + 0 = 1

    示例 2：
    输入：n = 3
    输出：2
    解释：F(3) = F(2) + F(1) = 1 + 1 = 2

    示例 3：
    输入：n = 4
    输出：3
    解释：F(4) = F(3) + F(2) = 2 + 1 = 3

  • 方法一
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
      def climbStairs(self, n):
          if n<=2:
              return n
          a = 1
          b = 2
          for i in range (2,n):
              tem = a
              a = b
              b = b +tem
          return b
    解析
    斐波那契数的边界条件是 F(0)=0 和 F(1)=1。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系： F(n)=F(n−1)+F(n−2)由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。 根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n−1) 与 F(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。
    复杂度分析
    时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
    空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。