动态规划 —— 斐波那契数列模型
LeetCode相关刷题
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程程(ಥ_ಥ)-CSDN博客
所属专栏：动态规划
我们只需要知道做题的步骤就行，也被称为动态规划五部曲。
1、明确dp数组及其下标所对应的含义；
2、递推公式；
3、如何初始化dp数组（避免下标越界问题）；
4、dp数组的遍历顺序（填充dp数组的顺序）；
5、打印dp数组（debug时才需要，看实际的dp数组哪里和我们认为的不一致）。
dp数组是用来存放状态的，递推公式可以计算出状态的演变。
目录
1137.第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 <= n <= 37- 答案保证是一个 32 位整数，即
answer <= 2^31 - 1。
思路：
dp数组是用来存放泰波那契序列的值的。
1、i 表示第i个元素下标，dp[i]表示第i个元素下标所对应的值；
2、递推公式题目已经给出来了： Tn = Tn-3 + Tn-2 + Tn-1（这样更直观）。
3、dp数组的初始化也是题目给出的，T0 = 0, T1 = 1, T2 = 1。
4、遍历的顺序是从左到右的（按照计算顺序来的）。
代码实现：
class Solution {
public int tribonacci(int n) {
// 判断特殊情况
if (n == 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
// dp数组用来存放数，dp[i]表示第i个泰波那契数
int[] dp = new int[n+1];
dp[0] = 0; // n可能为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];
}
}上述是基本做法，在此之上，还可以通过滚动数组进行空间优化。
0 1 1 2 4 7 13 ......
a b c使用三个变量去记录前三者的状态，然后持续更新即可
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;
for (int i = 3; i <= n; i++) {
int sum = a + b + c;
a = b;
b = c;
c = sum;
}
return c;
}
}面试题08.01.三步问题
题目：
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
示例 1：
输入：n = 3 输出：4 说明：有四种走法示例 2：
输入：n = 5 输出：13提示:
- n 范围在[1, 1000000]之间
思路：我们首先得明确dp数组以及下标的含义，然后再去求出推导公式，而推导公式需要我们根据示例进行推演变化而得出来。
1、确定dp[i]以及i下标的含义：
一般来说，dp[i]的含义都是有固定的模版的，最常见的就是："以i位置结尾，....(结合题目要求)"
这里dp[i]的含义是，到第i阶台阶，总共有多少种方式。2、推导公式：
推导公式也是有类似的模版的，"以i位置的状态为基准，分析离其最近一步的状态来分析问题"，这里的以i位置为基准，最近一步有：i-1、i-2、i-3
可以根据我们的推演过程，得出：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]3、如何初始化dp数组：
初始化dp数组是为了避免下标越界的问题，根据推导公式，我们可以得出，当i == 4时，推导公式才有意义，
因此我们需要手动初始化前面三个元素，dp[1]、dp[2]、dp[3]4、确定遍历顺序（填充dp数组的顺序）：
dp数组是从左到右进行填充的
5、打印dp数组：
代码实现：
class Solution {
public int waysToStep(int n) {
// 判断特殊情况
if (n == 1 || n == 2) {
return n;
}
if (n == 3) {
return 4;
}
int[] dp = new int[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]+dp[i-3])%1000000007)%1000000007;
}
return dp[n];
}
}空间优化版本：
class Solution {
public int waysToStep(int n) {
if (n == 1 || n == 2) {
return n;
}
if (n == 3) {
return 4;
}
int a = 1, b = 2, c = 4;
for (int i = 4; i <= n; i++) {
int sum = (a+((b+c)%1000000007))%1000000007;
a = b;
b = c;
c = sum;
}
return c;
}
}746.使用最小花费爬楼梯
题目：
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为
0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路：这里要明确题目所说的楼顶的意思，并不是指第 n-1 个位置，而是第 n 个位置，可以从示例1推理出，如果20是楼顶的话，那么从0下标走到达楼顶就只需要花费10元了，而不是15元了，因此楼顶只能是 n 下标所对应的位置。
1、确定dp[i]以及i的含义；
dp[i]表示到达第i阶楼梯的最少费用
2、推导公式；
到达dp[i]最近的一步是：dp[i-1]和dp[i-2]，dp[i-1]是到达第i-1阶楼梯的最少费用，dp[i-2]到达第i-2阶楼梯的最少费用，dp[i]的含义是到达第i阶楼梯的最少费用，可以表示为dp[i-1] + cost[i-1] 与 dp[i-2]+cost[i-2]的较小值
3、初始化dp数组；
为了确保数组不越界的话，得将dp[0]和dp[1]给提前初始化好，而根据题意可知：初始时，就是处于第0阶楼梯和第1阶楼梯，因此两者初始化为0即可
4、确定遍历顺序；
从左到右的给数组赋值即可。
5、打印dp数组
上述是最容易想到的，也是比较好解决的，除此之外，还有另外一种方法：
1、确定dp[i]以及i的含义；
dp[i]表示从i位置到达楼顶的最小费用
2、推导公式；
到达dp[i]最近的一步是：dp[i+1]和dp[i+2]，dp[i+1]是从i+1位置到达楼顶的最少费用，dp[i+2]是从i+1位置到达楼顶的最少费用，而dp[i]表示从i位置到达楼顶的最小费用，因此dp[i] = dp[i+1]+cost[i] 与 dp[i+2]+cost[i]的较小值。
3、初始化dp数组；将n-2位置和n-1位置初始化即可，初始化为cost[i-2]和cost[i-1]
4、确定遍历顺序；
从右往左给数组元素赋值
5、打印dp数组
代码实现：
dp[i]表示到达i位置所需的最少费用：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length; // 总共有n阶台阶[0, n-1]
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[n]; // 到第n阶台阶的最少费用，一定要跳出去
}
}dp[i]表示从i位置到达楼顶的最少费用：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length; // 总共有n阶台阶[0, n-1]
int[] dp = new int[n];
dp[n-1] = cost[n-1];
dp[n-2] = cost[n-2];
for (int i = n-3; i >= 0; i--) {
dp[i] = Math.min(dp[i+1], dp[i+2]) + cost[i];
}
// 返回 从0位置到达楼顶的的费用 与 从1位置到达楼顶的费用 的较小值
return Math.min(dp[0], dp[1]);
}
}91.解码方法
题目：
一条包含字母
A-Z的消息通过以下映射进行了 编码 ：
"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（
"2"和"5"与"25"）。例如，
"11106"可以映射为：
"AAJF"，将消息分组为(1, 1, 10, 6)"KJF"，将消息分组为(11, 10, 6)- 消息不能分组为
(1, 11, 06)，因为"06"不是一个合法编码（只有 "6" 是合法的）。注意，可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串
s，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回0。题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2：
输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。示例 3：
输入：s = "06" 输出：0 解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。提示：
1 <= s.length <= 100s只包含数字，并且可能包含前导零。
思路：
1、明确dp[i]以及i的含义;
dp[i]表示到达i位置时，总共的解码方案
2、推导公式;
最近的一步是：dp[i-1]配合dp[i]一起解码；dp[i]单独解码。但是解码不一定会成功，因此我们得做判断，如果解码成功的话，前者dp[i] += dp[i-2］，后者dp[i] += dp[i-1]。如果是失败的话，dp[i］= 0
3、如何初始化dp数组;
确保数组不越界的话，dp[0]和dp[1]需要初始化，dp[0]就是判断0位置的值是否在['1＇，‘9']之间，dp[1]就是判断能够单独解码，以及能否配合解码即可
4、遍历顺序;
从左到右对数组元素进行赋值
5、打印dp数组;
代码实现：
class Solution {
public int numDecodings(String s) {
int n = s.length();
char[] str = s.toCharArray();
int[] dp = new int[n];
// 判断第1个位置是否能单独解码
if (str[0] != '0') { // ['1', '9']可以单独解码
dp[0] = 1;
}
// 排除只有1个字符的情况
if (n == 1) {
return dp[0];
}
// 判断第二个位置是否可以单独解码，以及配合解码
if (str[1] != '0' && str[0] != '0') { // 单独解码(第一个位置也要可以)
dp[1] += 1;
}
// 配合解码就是指两者相加之和处于[10, 26]之间
// 前导0是不能解码的
int t = (str[0]-'0') * 10 + str[1] - '0';
if (t >= 10 && t <= 26) {
dp[1] += 1;
}
for (int i = 2; i < n; i++) {
// 判断 i 位置是否可以单独解码以及配合解码
if (str[i] != '0') {
dp[i] += dp[i-1];
}
t = (str[i-1] - '0') * 10 + str[i] - '0';
if (t >= 10 && t <= 26) {
dp[i] += dp[i-2];
}
}
// 返回n-1为结尾时，解码的总数
return dp[n-1];
}
}上述代码在求解第二个位置的值时，和for循环内求解值的流程是类似的，我们可以想办法把for循环外部的求解过程给去掉，通过for循环内部来实现。实现的方式是在创建dp数组时，多申请一个空间即可。
将dp数组的初始空间定义为n+1时，要注意下面两个地方：
1、当求dp[2]时，采用其中一种配合解码的方式，并且解码成功的话，dp[2] = dp[0]，如果我们将dp[0]初始化为0的话，那么这里明明就有一种解码方式，但是我们却忽略了，因此dp[0］要初始化为1。
2、由于dp数组的长度变了，因此与原始dp数组的下标映射关系也要发生变化，原来的0下标，映射到新dp数组的1下标。
当然上述代码也是可以的，不一定要去修改。
优化版本：
class Solution {
public int numDecodings(String s) {
int n = s.length();
char[] str = s.toCharArray();
int[] dp = new int[n+1];
dp[0] = 1; // 一定要初始化为1
// 判断第1个位置是否能单独解码
if (str[0] != '0') { // ['1', '9']可以单独解码
dp[1] = 1;
}
// 排除只有1个字符的情况
if (n == 1) {
return dp[1];
}
for (int i = 2; i <= n; i++) {
// 判断 i 位置是否可以单独解码以及配合解码
if (str[i-1] != '0') {
dp[i] += dp[i-1];
}
int t = (str[i-2] - '0') * 10 + str[i-1] - '0';
if (t >= 10 && t <= 26) {
dp[i] += dp[i-2];
}
}
// 返回n-1为结尾时，解码的总数
return dp[n];
}
}好啦！本期 动态规划——斐波那契数列模型 的刷题之旅 就到此结束啦！我们下一期再一起学习吧！
GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。
更多推荐
26
0- 0
已为社区贡献2条内容
所有评论(0)