【动态规划】斐波那契数列模型（C++）

目录

1137.第N个泰波那契数

解法（动态规划） 算法流程

1. 状态表⽰：

2. 状态转移⽅程：

3. 初始化：

4. 填表顺序：

5. 返回值：

 C++算法代码 

优化： 滚动数组

测试：

08.01.三步问题

解法（动态规划） 算法思路

1. 状态表⽰

2. 状态转移⽅程

3. 初始化

4. 填表顺序

5. 返回值

代码：

测试

746.使⽤最⼩花费爬楼梯

2. 状态转移⽅程：

3. 初始化：

测试：

 91.解码⽅法

算法思路：

1. 状态表⽰：

2. 状态转移⽅程：

3. 初始化：

代码： 

优化

测试

---

1137.第N个泰波那契数

解法（动态规划） 算法流程

1. 状态表⽰：

这道题可以「根据题⽬的要求」直接定义出状态表⽰：

dp[i] 表⽰：第i 个泰波那契数的值。

2. 状态转移⽅程：

题⽬已经⾮常贴⼼的告诉我们了： 

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

3. 初始化：

从我们的递推公式可以看出， dp[i] 在 i = 0 以及i = 1 的时候是没有办法进⾏推导的，因 为dp[-2] 或dp[-1] 不是⼀个有效的数据。

因此我们需要在填表之前，将0, 1, 2 位置的值初始化。题⽬中已经告诉我们dp[0] = 0, dp[1] = dp[2] = 1 。

4. 填表顺序：

毫⽆疑问是「从左往右」。

5. 返回值：

应该返回dp[n] 的值。

 C++算法代码 

使⽤⼀维数组：

class Solution {public:    int tribonacci(int n) {        //如何填，抄状态转移方程        if(n==0||n==1)        return n;        vector dp(n+1);        dp[0]=0,dp[1]=1,dp[2]=1;//初始化前三个        //left->right        for(int i=3;i