【动态规划】斐波那契数列模型
📝前言说明：
- 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行不同专题的动态规划的学习
| 点击链接 | 开始学习 |
|---|---|
| 斐波那契数列模型 | 路径问题 |
| 简单多状态（一） | 简单多状态（二） |
| 子数组系列（一） | 子数组系列（二） |
| 子序列问题（一） | 子序列问题（二） |
| 回文串（一） | 回文串（二） |
| 两个数组dp问题（一） | 两个数组的dp问题（二） |
| 01背包问题 | 完全背包 |
| 二维的背包问题 | 其他 |
题单汇总链接：点击 → 题单汇总
题目
动态规划要点
动态规划的核心思想是将问题分解为相互关联的子问题，通过求解子问题并利用子问题的解来构造原问题的解，同时避免重复计算子问题。
动态规划分成五大要点，这五点都和要创建的dp表有关，dp表可以帮助我们快速得到题目答案：
- 状态表示（重点）
- 是什么？：dp[i]的值所代表的含义
- 怎么得到？（对于线性的dp问题：经验 + 题目分析）
- 经验：以某一个位置为结尾 / 为开头，怎样怎样
- 再根据题目要求分析，发现子问题（填充，怎样怎样）
- 状态转移方程（难点）
- 即：dp[i]等于什么
- 初始化
- 初始化，并且保证填表的时候不越界
- 填表顺序
- 返回值
- 根据题目要求，通过状态表示得到
空间优化（这个属于在能解决问题的基础上，进行算法优化了，不是我们前期的目标）
但是第1137 讲一下
1137. 第 N 个泰波那契数
题目链接：https://leetcode.cn/problems/n-th-tribonacci-number/description/
动态规划第一题，好好捋一下思路。
优质解
思路：
- 状态表示：
dp[i]表示第 i 个泰波那契数 - 状态转移方程：
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] - 初始化：
dp[0] = 0; dp[1] = 1; dp[2] = 1 - 填表顺序：从左往右
- 返回值：
dp[n]
代码：
classSolution{public:inttribonacci(int n){// 处理特殊情况if(n ==0)return0;if(n ==1|| n ==2)return1; vector<int>dp(n +1); dp[0]=0; dp[1]=1; dp[2]=1;// 初始化for(int i =3; i <= n; i++) dp[i]= dp[i -3]+ dp[i -2]+ dp[i -1];// 从左往右填表return dp[n];}};时间复杂度：
空间复杂度：
本题的空间优化：
利用滚动数组，只记录前三个数的值（因为计算第 i 个数，只需要前三个数的值）
优化后的代码：
classSolution{public:inttribonacci(int n){// 处理特殊情况if(n ==0)return0;if(n ==1|| n ==2)return1;int a =0, b =1, c =1, ans =0;// 初始化for(int i =0; i <= n -3; i++){ ans = a + b + c; a = b; b = c; c = ans;}return ans;}};面试题 08.01. 三步问题
题目链接：https://leetcode.cn/problems/three-steps-problem-lcci/description/
优质解
思路：
- 状态表示：
dp[i]表示：到第i个台阶的总方法数 - 状态转移方程：
- 首先，我们要搞清楚：只要有一步不同就是不同方案
- 那么，假如此时在 i 位置，则从
i - 3、i - 2、i - 1都可以到 位置i- 从
i - 3到i：直接走三步（一种方法），注意，这里不能选择走一步和两步，一维会走到i - 2和i - 1上，这时候就不是不同方案了 i - 2到i：直接走两步（一种方法）i - 1到i：走一步（一种走法，也就是说：最后一步如果这么走，那其实方法的总数就等于dp[i - 1]）
- 从
- 方程：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
- 初始化：
dp[1] = 1； dp[2] = 2; dp[3] = 4; - 填表顺序：从左往右，线性的
- 返回值：
dp[n]
代码：
classSolution{public:intwaysToStep(int n){// 处理边界情况if(n ==1|| n ==2)return n;if(n ==3)return4; vector<int>dp(n +1); dp[1]=1; dp[2]=2; dp[3]=4;for(int i =4; i <= n; i++) dp[i]=((dp[i -1]+ dp[i -2])%1000000007+ dp[i -3])%1000000007;// 每次相加都% 防止溢出return dp[n];}};时间复杂度：O(n)
空间复杂度：O(n)
746. 使用最小花费爬楼梯
题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
个人解
思路：
- 状态表示：
dp[i]爬到第i个台阶的最小费用 - 状态转移方程：
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); - 初始化：
dp[0] = 0; dp[1] = 0; - 填表顺序：从左往右
- 返回值：
dp[n]
用时：3:00
屎山代码：
classSolution{public:intminCostClimbingStairs(vector<int>& cost){int n = cost.size(); vector<int>dp(n +1); dp[0]=0; dp[1]=0;for(int i =2; i <= n; i++) dp[i]=min(dp[i -1]+ cost[i -1], dp[i -2]+ cost[i -2]);return dp[n];}};时间复杂度：O(n)
空间复杂度：O(n)
91. 解码方法
题目链接：https://leetcode.cn/problems/decode-ways/description/
个人解
思路：
// 状态表示 dp[i]: 前 i 个字符能凑成的组合总数 // 状态转移方程（只有能和其他数组合的时候，才有可能有新组）: // dp[i] = dp[i - 1]，当：s[i] 属于[1, 9]，且s[i - 1]和s[i]组合不能成 // dp[i] = dp[i - 1] + 1 当：s[i] 属于[1, 9]，且s[i - 1]和s[i]组合能成 // 特殊判断，s[i] == '0' 的情况，如果能和s[i - 1]组成，则dp[i] = dp[i - 1]，如果不能组成则：不是合法编码 // 初始化: 如果s[0] 属于 [1, 9]，则dp[0] == 1; // 填表顺序: 从左往右 // 返回值: dp[n] 用时：20:00
屎山代码（通过237 / 269，但是数量的增加不是简单的+1关系，我没找到正确关系），以下为未通过的错误代码：
classSolution{public:intnumDecodings(string s){if(s[0]=='0')return0;int n = s.size(); vector<int>dp(n); dp[0]=1;for(int i =1; i < n; i++){int numi = s[i]-'0';// 字符转数字int numj = s[i -1]-'0';if(numi ==0)// 对 0 特殊处理if(numj <1|| numj >2)return0;// 不能和前面的数组合else dp[i]= dp[i -1];elseif((numj !=0&& numj *10+ numi <=26)&&!(i +1< n && s[i +1]=='0')){ dp[i]= dp[i -1]+1;}else dp[i]= dp[i -1];}return dp[n -1];}};优质解
思路（类似爬楼梯）：
- 状态转移方程：当能和前面的数组合时，
dp[i] = dp[i - 1] + dp[i - 2]，当前位属于 1-9 时，可+ dp[i - 1]，能和前面的数组成的时候，可+ dp[i - 2] - 根本不用特殊处理
0，因为0的结果也会体现在dp[i]上
代码：
classSolution{public:intnumDecodings(string s){int n = s.size(); vector<int>dp(n);// 创建⼀个 dp表// 初始化前两个位置 dp[0]= s[0]!='0';if(n ==1)return dp[0];// 处理边界情况if(s[1]<='9'&& s[1]>='1') dp[1]+= dp[0];int t =(s[0]-'0')*10+ s[1]-'0';if(t >=10&& t <=26) dp[1]+=1;// 填表for(int i =2; i < n; i++){// 如果单独编码if(s[i]<='9'&& s[i]>='1') dp[i]+= dp[i -1];// 如果和前面的⼀个数联合起来编码int t =(s[i -1]-'0')*10+ s[i]-'0';if(t >=10&& t <=26) dp[i]+= dp[i -2];}// 返回结果return dp[n -1];}};时间复杂度：O(n)
空间复杂度：O(n)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
