当前位置：首页 > java >正文

【动态规划】斐波那契数列模型

java 2025/5/13 12:59:02

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

斐波那契数列模型

题目

动态规划要点
1137. 第 N 个泰波那契数
- 优质解
面试题 08.01. 三步问题
- 优质解
746. 使用最小花费爬楼梯
- 个人解

动态规划要点

动态规划分成五大要点，这五点都和要创建的dp表有关，dp表可以帮助我们快速得到题目答案：

状态表示（重点）
- 是什么？：dp[i]的值所代表的含义
- 怎么得到？
  - 题目要求
  - 经验 + 题目分析
    - 经验：以某一个位置为结尾 / 为开头根据题目要求来分析
  - 分析问题时，发现重复子问题
状态转移方程（难点）
- 即：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]

代码：

class Solution {
public:int tribonacci(int n) {// 处理特殊情况if(n == 0) return 0;if(n == 1 || n == 2) return 1; 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 个数，只需要前三个数的值）
在这里插入图片描述
优化后的代码：

class Solution {
public:int tribonacci(int n) {// 处理特殊情况if(n == 0) return 0;if(n == 1 || n == 2) return 1; 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]

代码：

class Solution {
public:int waysToStep(int n) {// 处理边界情况if(n == 1 || n == 2) return n;if(n == 3) return 4;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
屎山代码：

class Solution {
public:int minCostClimbingStairs(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];}
};