算法：[动态规划] 斐波那契数列模型

目录

题目一：第 N 个泰波那契数

题目二：三步问题

题目三：最小花费爬楼梯

题目四：解码方法

题目一：第 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

提示：

• 0 3

  ②直接从1号到3号，怎么到1号不管，但必须经过1号台阶：0 -> 1 -> 3

  ③④直接从2号到3号，怎么到2号不管，但必须经过2号台阶，因为前面的 2 中，已经说明了想上2号台阶有2种方式，所以有2种方式方式：

  0 -> 2 -> 3；0 -> 1 -> 2  -> 3

  4、想上4号台阶：7种方式

  ①直接从1号到4号，因为从0到不了，那就从1到4号台阶，怎么到1号不管，但必须经过1号台阶，而0到1的方式上面也说到了有1种方式，所以从1号到4号有1种方式：

  0 -> 1 -> 4

  ②③直接从2号到4号，怎么到2不管，前面也说到了从0号到2号有2种方式，所以从2号到4号也有2种方式：

  0 -> 2 -> 4；0 -> 1 -> 2 -> 4

  ④⑤⑥⑦直接从3到4，同理，怎么到3不管，前面从0到3的方式有4种，所以这里也是4种方式

  ---

  所以下面根据上面所说的原理，列出dp表：

  

  我们发现，到1、2、3号台阶的方式数量一旦直到，那么到第4号台阶的方式数量就是到1、2、3号台阶的方式数量之和，到5号台阶数量也是一样

  所以继续动态规划的五步：

  ①状态表示

  通过经验 + 题目要求，理解为：以 i 位置为结尾， ........，可以得知：

  dp[i] 表示到达第 i 个台阶时，一共有多少种方法

  ②状态转移方程

  依旧是通过经验，我们需要以 i 位置的状态，最近的一步来划分问题

  由于这道题中的小孩一次能跨1阶、2阶或3阶，所以最近的一步就是从 i-1、i-2、i-3位置到 i 位置

  因为从 i-3 位置到 i 位置一步就能跨到，所以只需知道从地面到 i-3 位置需要多少种方式即可，而 dp[i-3] 就是到达第 i-3 个台阶时，一共有多少种方法，所以从 i-3 位置到 i 位置就转化为了 dp[i-3] 

  i-1、i-2 位置到 i 位置同理可得：dp[i-1]、dp[i-2]，所以状态转移方程就是：

  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

  ③初始化

  初始化就为了填表的时候不越界，这道题是从1位置开始的，dp[0]是无意义的，所以dp[1]、dp[2]、dp[3]是会越界的，所以需要将dp[1]、dp[2]、dp[3]初始化，在上面讲述时计算了到3个台阶的方式数量，所以初始化为：

  dp[1] = 1，dp[2] = 2，dp[3] = 4

  ④填表顺序

  这道题填表顺序依旧是从左往右

  ⑤返回值

  题目要求返回到 n 位置时，有多少种方式，而dp[n]正好就是这种意义

  所以返回dp[n]即可

  ---

  在初始化前，需要处理边界情况，因为n的范围是是：[1, 1000000]，而我们需要初始化1、2、3，如果 n 为1，就会越界，所以需要处理边界条件

  这里同样可以使用滚动数组进行优化，这里就不实现了，比较简单，和题目一中的优化几乎一摸一样，实现代码如下：

  class Solution {
  public:
      int waysToStep(int n) 
      {
          // 1、创建dp表
          // 2、填表前初始化
          // 3、填表
          // 4、求返回值
          //每次加法需要对MOD取模
          const int MOD = 1e9 + 7;
          if(n == 1 || n == 2) return n;
          if(n == 3) return 4;
          vector dp(n + 1);
          dp[1] = 1, dp[2] = 2, dp[3] = 4;
          for(int i = 4; i