动态规划 - 斐波那契数列模型
斐波那契数列模型
动态规划中的斐波那契数列模型，本质上是一类具有递推关系和重叠子问题特征的问题。这类问题的核心是：当前状态的值可以由前几个状态推导出来。
适用题目类型包括：
基础型
-
直接求斐波那契数列第 n 项。
-
变形：爬楼梯（每次 1 或 2 步）、矩形覆盖（用 1×2 或 2×1 骨牌铺满 2×n 的区域）——本质是斐波那契递推式
f(n) = f(n-1) + f(n-2)。
多决策路径型
-
每次可选择的前进方式更多，如爬楼梯可以一次爬 1、2、3 步，则递推式变为
f(n) = f(n-1) + f(n-2) + f(n-3)。
带约束或条件型
-
如“不能连续执行某种操作”：打家劫舍中不能偷相邻的房子，递推式为
f(i) = max(f(i-1), f(i-2) + nums[i])，仍是前两状态决定当前状态。
二维或路径型扩展
-
某些网格路径问题，如果只能向右或向下走，到达 (i,j) 的路径数
dp[i][j] = dp[i-1][j] + dp[i][j-1]，可视作二维斐波那契思想。
判断关键：
-
问题能分解为相似的子问题；
-
当前解依赖于前面有限个已解决的子问题（通常是前 1~3 个）；
-
有明显的状态转移方程。
这类题目的动态规划解法通常用数组或几个变量迭代，时间复杂度 O(n)，空间可优化到 O(1)。
题目练习
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
解法（动态规划）
算法流程
状态表示： 这道题可以「根据题目的要求」直接定义出状态表示：
- dp[i] 表示：第 i 个泰波那契数的值。
状态转移方程： 题目已经非常贴心的告诉我们了：
- dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
初始化：
从我们的递推公式可以看出，dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进行推导的，因为 dp[-2] 或 dp[-1] 不是一个有效的数据。因此我们需要在填表之前，将 0，1，2 位置的值初始化。题目中已经告诉我们 dp[0] = 0，dp[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;
int a = 0, b = 1, c = 1, d = 0;
while(n > 2)
{
d = a + b + c;
a = b; b = c; c = d;
n--;
}
return d;
}
};
面试题 08.01. 三步问题 - 力扣（LeetCode）
解法（动态规划）
算法思路
状态表示
这道题可以根据「经验+题目要求」直接定义出状态表示：
- dp[i] 表示：到达 i 位置时，一共有多少种方法。
状态转移方程
以i位置状态的最近的一步，来分情况讨论： 如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么它应该等于所有i-步的方式之和：
综上所述，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。 在计算的时候，三个值全部加起来再取模，即 (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD 是不可取的，同学们可以试验一下，n 取题目范围内最大值时，网站会报错 signed integer overflow。 对于这类需要取模的问题，我们每计算一次（两个数相加/乘等），都需要取一次模。否则，万一发生了溢出，我们的答案就错了。
- 上一步上一级台阶，dp[i] += dp[i - 1]；
- 上一步上两级台阶，dp[i] += dp[i - 2]；
- 上一步上三级台阶，dp[i] += dp[i - 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。
填表顺序
毫无疑问是「从左往右」。
返回值
应该返回 dp[n] 的值。
class Solution {
public:
const long long MOD = 1e9 + 7; // 1e7
int waysToStep(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
long long a = 1, b = 2, c = 4, d = 0;
while(n > 3)
{
d = (a + ( b + c) % MOD) % MOD;
a = b; b = c; c = d;
n--;
}
return d;
}
};
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
解法（动态规划）
算法思路
解法一：
状态表示
这道题可以根据「经验+题目要求」直接定义出状态表示：
- 第一种：以 i 位置为结尾，巴拉巴拉
- dp[i] 表示：到达 i 位置时的最小花费。（注意：到达 i 位置的时候，i 位置的钱不需要算上）
状态转移方程
根据最近的一步，分情况讨论：
- 先到达 i - 1 的位置，然后支付 cost[i - 1]，接下来走一步走到 i 位置：dp[i - 1] + cost[i - 1]；
- 先到达 i - 2 的位置，然后支付 cost[i - 2]，接下来走一步走到 i 位置：dp[i - 2] + cost[i - 2]。
初始化
从我们的递推公式可以看出，我们需要先初始化 i = 0，以及 i = 1 位置的值。容易得到 dp[0] = dp[1] = 0，因为不需要任何花费，就可以直接站在第 0 层和第 1 层上。
填表顺序
根据「状态转移方程」可得，遍历的顺序是「从左往右」。
返回值
根据「状态表示以及题目要求」，需要返回 dp[n] 位置的值。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
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];
}
};
解法二：
状态表示： 这道题可以根据「经验+题目要求」直接定义出状态表示：
-
第二种：以 i 位置为起点，巴拉巴拉。
-
dp[i] 表示：从 i 位置出发，到达楼顶，此时的最小花费。
状态转移方程： 根据最近的一步，分情况讨论：
-
支付 cost[i]，往后走一步，接下来从 i + 1 的位置出发到终点：dp[i + 1] + cost[i]；
-
支付 cost[i]，往后走两步，接下来从 i + 2 的位置出发到终点：dp[i + 2] + cost[i]； 我们要的是最小花费，因此 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]。
初始化： 为了保证填表的时候不越界，我们需要初始化最后两个位置的值，结合状态表示易得：dp[n - 1] = cost[n - 1]，dp[n - 2] = cost[n - 2]。
填表顺序： 根据「状态转移方程」可得，遍历的顺序是「从右往左」。
返回值： 根据「状态表示以及题目要求」，需要返回 dp[n] 位置的值。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n);
dp[n - 1] = cost[n - 1];
dp[n - 2] = cost[n - 2];
for(int i = n - 3; i >= 0; i--)
{
dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
}
return min(dp[0], dp[1]);//注意
}
};
91. 解码方法 - 力扣（LeetCode）
解法（动态规划）
算法思路：
类似于斐波那契数列。
状态表示： 根据以往的经验，对于大多数线性 dp，我们经验上都是「以某个位置结束或者开始」做文章，这里我们继续坚持「用 i 位置为结尾」，结合「题目要求」来定义状态表示。
- dp[i] 表示：字符串中 [0，i] 区间上，一共有多少种编码方法。
状态转移方程： 定义好状态表示，我们就可以分析 i 位置上的 dp 值，如何由「前面」或者「后面」的信息推导出来： 关于 i 位置的编码状况，我们可以分为下面两种情况：
下面我们就上面的两种解码情况，继续分析：
综上所述：dp[i] 最终的结果应该是上面四种情况下，解码成功的两种的累加和（因为我们关心的是解码方法，既然解码成功，就不再加入到最终结果中去），因此可以得到状态转移方程（dp[i] 默认初始化为 0）：
- 让 i 位置上的数单独编码成一个字符；
- 让 i 位置上的数与 i - 1 位置上的数结合，解码成一个字符。
让 i 位置上的数单独解码成一个字母，就存在「解码成功」和「解码失败」两种情况：
- 解码成功：当 i 位置上的数在 [0，9] 之间的时候，说明 i 位置上的数是可以单独编码的，那么此时 [0，i] 区间上的解码方法应该等于 [0，i - 1] 区间上的解码方法。因为 [0，i - 1] 区间上的所有解码结果，后面填上一个 i 位置解码后的字母就可以了。此时 dp[i] = dp[i - 1]；
- 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0，i] 区间上不存在解码方法。因为 i 位置如果单独参与解码，但是解码失败了，那么前面做的努力就全部白费了。此时 dp[i] = 0。
让 i 位置上的数与 i - 1 位置上的数结合在一起，解码成一个字母，也存在「解码成功」和「解码失败」两种情况：
- 解码成功：当结合的数在 [10，26] 之间的时侯，说明 [i - 1，i] 两个位置是可以解码成功的，那么此时 [0，i] 区间上的解码方法应该等于 [0，i - 2] 区间上的解码方法，原因同上。此时 dp[i] = dp[i - 2]；
- 解码失败：当结合的数在 [0，9] 和 [27，99] 之间的时候，说明两个位置结合后解码失败（这里一定要注意 00 01 02 03 04……这几种情况），那么此时 [0，i] 区间上的解码方法就不存在了，原因依旧同上。此时 dp[i] = 0。
i. 当 s[i] 上的数在 [1，9] 区间上时：dp[i] += dp[i - 1]；
ii. 当 s[i - 1] 与 s[i] 上的数结合后，在 [10，26] 之间的时候：dp[i] += dp[i - 2]； 如果上述两个判断都不成立，说明没有解码方法 dp[i] 就默认为 0。
初始化： 由于可能要用到 i - 1 以及 i - 2 位置上的 dp 值，因此要先初始化「前两个位置」。
方法二（添加辅助位置初始化）： 可以在最前面加一个辅助点，帮助我们初始化。使用这种技巧要注意两个点：
初始化 dp[0]：
- 当 s[0] == '0' 时，没有编码方法，结果 dp[0] = 0；
- 当 s[0] != '0' 时，能编码成功，dp[0] = 1；
初始化 dp[1]：
- 当 s[1] 在 [1,9] 之间时，能单独编码，此时 dp[1] = dp[0]（原因同上，dp[1] 默认为 0）；
- 当 s[0] 与 s[1] 结合后的数在 [10，26] 之间时，说明在前两个字符中，又有一种编码方式，此时 dp[1] += 1；
i. 辅助结点里面的值要保证后续填表是正确的；
ii. 下标的映射关系。
填表顺序： 毫无疑问是「从左往右」。
返回值： 应该返回 dp[n - 1] 的值，表示在 [0，n - 1] 区间上的编码方法。
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(n == 1) return s[0] == '0' ? 0 : 1;
vector<int> dp(n);
dp[0] = s[0] != '0';
if(s[0] != '0' && s[1] != '0') dp[1]++;
int t = (s[0] - '0') * 10 + s[1] - '0';
if(t >= 10 && t <= 26) dp[1]++;
for(int i = 2; i < n; ++i)
{
int a = s[i] - '0', b = s[i - 1] - '0';
int t = b * 10 + a;
if(a) dp[i] += dp[i - 1];
if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
}
return dp[n - 1];
}
};
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
23
0- 0
已为社区贡献32条内容
所有评论(0)