《算法闯关指南：动态规划算法--斐波拉契数列模型》--01.第N个泰波拉契数，02.三步问题
🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！
🎬 博主简介：
文章目录
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
01.第N个泰波拉契数
题目链接：
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
题目描述：
题目示例：
解法（动态规划）：
算法流程：
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++算法代码：
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]=dp[2]=1;for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}return dp[n];}};滚动数组空间优化（了解即可）：
classSolution{public:inttribonacci(int n){//处理边界if(n==0)return0;if(n==1||n==2)return1;//滚动数组优化int a=0,b=1,c=1,d=0;for(int i=3;i<=n;i++){ d=a+b+c;//滚动操作 a=b,b=c,c=d;}return d;}};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
02.三步问题
题目链接：
面试题 08.01. 三步问题 - 力扣（LeetCode）
题目描述：
题目示例：
解法（动态规划）：
算法思路：
1. 状态表示：
这道题可以根据【经验+题目要求】直接定义出状态表示：dp[i] 表示：到达 i 位置时，一共有多少种方法。
2. 状态转移方程：
以 i 位置状态的最近的一步，来分情况讨论：
如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么他应等于所有上一步的方式之和：
- 上一步上一级台阶：
dp[i] += dp[i-1]； - 上一步上两级台阶：
dp[i] += dp[i-2]； - 上一步上三级台阶：
dp[i] += dp[i-3]；
综上所述，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。
在计算的时候，三个值全部加起来再取模是不行的，大家可以自己取试试。对于这类问题，我们每计算一次（两个数相加/乘等），都需要取一次模。否则，万一发生了溢出，我们的答案就错了。
3. 初始化
从我们的递推公式可以看出，dp[i] 在 i=0,i=1 以及 i=2 的时候是没有办法进行推导的，因为 dp[-3]dp[-2] 或 dp[-1] 不是一个有效的数据。
因此我们需要在填表之前，将 1，2，3 位置的值初始化。
根据题意，dp[1] = 1，dp[2] = 2，dp[3] = 4。
4. 填表顺序
毫无疑问是【从左往右】。
5. 返回值
应该返回 dp[n] 的值。
C++算法代码：
classSolution{public:intwaysToStep(int n){// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回constint MOD=1e9+7;// 处理边界情况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])%MOD+dp[i-3])%MOD;return dp[n];}};滚动数组空间优化（了解即可）：
classSolution{public:intwaysToStep(int n){// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回constint MOD=1e9+7;// 处理边界情况if(n==1||n==2)return n;if(n==3)return4;//空间优化int a=1,b=2,c=4,d=0;for(int i=4;i<=n;i++){ d=((a+b)%MOD+c)%MOD; a=b,b=c,c=d;}return d;}};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
结尾：
🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！ 结语：本文聚焦动态规划算法实战，通过两道经典题目《第N个泰波拉契数》和《三步问题》系统讲解动态规划的核心思路。 泰波拉契数：定义状态dp[i]表示第i个数的值，状态转移方程为dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，通过初始化边界和填表顺序（从左到右）求解，并提供滚动数组优化代码。 三步问题：状态dp[i]表示到达i台阶的方法数，转移方程为dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，强调取模防止溢出，并给出空间优化方案。
✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど
