【动态规划】斐波那契数列模型
文章目录
- 【动态规划】斐波那契数列模型
- 前言
- 一、第 N 个泰波那契数
- 二、三步问题
- 三、使用最小花费爬楼梯
- 四、解码方法
- 总结
前言
我们将深入探讨解决斐波那契数列模型相关问题的解决方法。通过一系列精心挑选的例题，我们将展示如何运用DP的核心原则来解决各种编程挑战，从泰波那契数的计算到楼梯爬升问题，再到解码方法的多样性。每个问题都将通过状态表示、状态转移方程、初始化、填表顺序和返回值的详细分析来解构，旨在提供一个清晰的算法实现框架，帮助读者掌握DP的精髓，并在实际编程中灵活运用。
一、第 N 个泰波那契数
题目链接：第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
算法流程：
- 状态表示
由题给出的要求：返回第 n 个泰波那契数 Tn 的值，所以确定 dp[i] 表示：第 i 个泰波那契数的值
- 状态转移方程
对题中给出的递推公式：Tn+3 = Tn + Tn+1 + Tn+2，两边同时令n = n-3时，可得Tn = Tn-3 + Tn-2 + Tn-1，所以我们可以得到状态转移方程：
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
- 初始化
由状态转移方程可知，数组下标不能小于0，故 i 的取值最小为 i = 3，所以我们在填表之前需要将 0,1,2 的位置值初始化。由题中给出 T0， T1， T2 的值，即可初始化：dp[0] = 0, dp[1] = dp[2] = 1
- 填表顺序
从左往右
- 返回值
要求Tn的值，应该返回 dp[n] 的值
示例代码：
int tribonacci(int n)
{
// 注意提前处理边界条件，避免访问越界
if (n == 0) { return 0; }
if (n == 1 || n == 2) { return 1; }
// 滚动数组节约空间
size_t a = 0, b = 1, c = 1;
size_t result = a + b + c;
for (int i = 3; i < n; ++i)
{
a = b;
b = c;
c = result;
result = a + b + c;
}
return result;
}
二、三步问题
题目链接：三步问题
有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
实现一种方法，计算小孩有多少种上楼梯的方式。
结果可能很大，你需要对结果模1000000007。
提示:
n范围在[1, 1000000]之间
算法流程：
- 状态表示
dp[i] 表示：到达 i 位置时，一共有多少种方法
- 状态转移方程
由于 dp[i] 表示一共多少中方式可以到 i 位置，且题目规定一次可以上1,2,3个台阶，所以得到状态转移方程：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
需要注意这里由于题目列出计算出结果的数据量可能过大，需要对结果的可能数作取模运算，所以尽量在三项中每两项相加后就进行一次取模运算，避免数据溢出。即为dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007
- 初始化
从我们的状态转移方程可以看出，方程中 i 的取值最小为3，但是题目中给出的提示：n的取值大于等于1，所以 i 的最小取值应该为4，接着可以通过上面的递推公式陆续推导出其他下标位置的值。那么初始化：dp[1] = 1, dp[2] = 2, dp[3] = 4
- 填表顺序
从左往右
- 返回值
应该返回 dp[n] 的值
示例代码：
int waysToStep(int n) {
// 递推公式 Tn = T<n-1> + T<n-2> + T<n-3>
size_t a = 1, b = 2, c = 4;
if (n == 1) { return a; }
else if (n == 2) { return b; }
else if (n == 3) { return c; }
size_t result = 0;
for (size_t i = 4; i <= n; i++)
{
result = ((a + b) % 1000000007 + c) % 1000000007;
a = b;
b = c;
c = result;
}
return result;
}
三、使用最小花费爬楼梯
题目链接：使用最小花费爬楼梯
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为
0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
注意：这里cost[n]对应的每个下标表示的都是楼层，而楼顶需要到达下标为n的位置，即一共 n+1 个位置。
算法流程：
- 状态表示
dp[i] 表示：到达 i 位置时的最小花费。（注意：这里i可以取n，所以数组长应该设为n+1）
- 状态转移方程
由题我们得知，每次跨越单位可以是1或2，所以 dp[i] 的值应该是一步前的位置对应的已花费金额+从一步前位置到该位置cost金额 与 两步前的位置对应的已花费金额+从两步前位置到该位置cost金额 相比的最小值
- 初始化
从状态转移方程可以看出，我们需要初始化 i = 0 和 i = 1位置的值，由题：dp[0] = dp[1] = 0
- 填表顺序
从左往右
- 返回值
根据我们前面的推导，数组应该初始化长度为n+1，返回值为 dp[n]，而非 dp[n - 1]
示例代码：
int minCostClimbingStairs(vector<int>& cost) {
size_t n = cost.size();
vector<int> dp(n + 1, 0);
// dp[i]表示到第i位置的最小花费
// dp[i] = min(dp[i - 1]+cost[i - 1], dp[i - 2]+cost[i - 2])
// 1.初始化
dp[0] = dp[1] = 0;
// 2.填表
for (size_t i = 2; i <= n; i++)
{
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
四、解码方法
题目链接：解码方法
一条包含字母
A-Z的消息通过以下映射进行了 编码 ：'A' -> "1" 'B' -> "2" ... 'Z' -> "26"要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，
"11106"可以映射为：
"AAJF"，将消息分组为(1 1 10 6)"KJF"，将消息分组为(11 10 6)注意，消息不能分组为
(1 11 06)，因为"06"不能映射为"F"，这是由于"6"和"06"在映射中并不等价。给你一个只含数字的 非空 字符串
s，计算并返回 解码 方法的 总数 。题目数据保证答案肯定是一个 32 位 的整数。
算法流程：
- 状态表示
由于我们需要遍历整个字符串才能做出判断，那么不妨设定以 i 位置为结尾，一共有多少种解码方法，所以：dp[i] 表示：字符串中 [0, i] 区间一共有多少种解码方法
- 状态转移方程
根据我们前面分析的 i 位置状态表示，我们在考虑 i 位置时已经将 i - 1 位置的数字纳入考虑范围，因为题中给出的解码条件可以单独解码，也可以和 i - 1 位置联合解码。所以我们不必在分析 i - 1 位置时考虑 (i - 1) + 1 位置的值是否可以与自身进行联合编码，这正是因为在分析 i 位置时自然会分析 i - 1 位置。
关于 i 位置的解码情况，可以分为单独解码和联合解码两种方式：
- **单独解码：**单独考虑 i 位置上的数可以解码为一个字母。
- **联合解码：**让 i 位置的数与 i - 1 位置的数结合，解码成一个字母。
<1> 让 i 位置上的数单独解码，存在解码成功与失败
- 解码成功：当 i 位置上的数在
[1, 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
<2> 让 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
综上所述：dp[i] 最终的结果应该是上面两两成功与失败的情况下，解码成功的两种情况的累加和。因此可以得到状态转移方程：
- 当 s[i] 上的数在 [1, 9] 区间上时：dp[i] += dp[i - 1]
- 当 s[i - 1] 与 s[i] 上的数结合后，在 [10, 26] 之间的时候： dp[i] += dp[i - 2]
- 如果上面两种情况都不满足，说明没有解码方法：dp[i] = 0
**注意：**上面为何设定 dp[i] += dp[i-1] (或 dp[i-2] )，究其原因是为了适应 dp[i] 位置被提前初始化为0的情况，同时避免因为对单独解码和联合解码的逻辑处理先后引起 dp[i] 数值不理想的情况。（例如可以单独解码但是不能联合解码，按照上面情况推断的逻辑需要对 dp[i] 先后赋值为 dp[i-1], 0 ，但是显然可以单独编码这里却因为对逻辑判断的顺序导致了 dp[i] 处值被错误置0的情况）
- 初始化
由状态转移方程可知，要推导其他位置的值首先需要用到 i - 1, i - 2 位置的dp值，因此需要初始化 dp[0], dp[1] 的值。
对 0,1 位置初始化时，同样需要遵循单独解码与联合解码的要求：
<1> 对 dp[0]:
当 s[0] == ‘0’ 时，没有解码方法，dp[0] = 0
当 s[0] != ‘0’ 时，能单独解码成功，dp[0] = 1
<2> 对 dp[1]:
当 s[1] 在 [1, 9] 之间时，能单独解码，此时 dp[i] += dp[i - 1] （这里dp[0] 的值不论等于1还是0，利用+=刚好可以对应if/else的两种分支对 dp[1] 赋值的情况）
当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明前两个字符又能组成联合编码，由于 dp[-1] 不存在，所以制定赋值此时 dp[1] += 1
- 填表顺序
从左往右
- 返回值
应该返回 dp[n - 1] 的值，因为遍历完字符串中最后一位数字才算结束，表示在 [0, n-1] 区间上总共的解码方法
示例代码：
int numDecodings(string s) {
// dp[i]表示第i位置解码方法总数
// 解码方式分两种：1.第i位单独解码 2.第i-1位与第i位组合解码
int n = s.size();
vector<int>dp(n, 0);
// 1.初始化
dp[0] = s[0] == '0' ? 0 : 1;
if (n == 1) { return dp[0]; } // 防止后续越界
if (s[1] <= '9' && s[1] >= '1') { dp[1] += dp[0]; } // i=0、1分别解码算一种方法
int val = (s[0] - '0') * 10 + (s[1] - '0');
if (val <= 26 && val >= 10) { dp[1] += 1; }
for (int i = 2; i < n; i++)
{
// 单独解码
if (s[i] <= '9' && s[i] >= '1') { dp[i] += dp[i - 1]; }
// 与前一位联合解码
val = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (val <= 26 && val >= 10)
{
dp[i] += dp[i - 2];
}
}
return dp[n - 1];
}
总结
对于诸如此类的线性dp数组的题型，最大的共性就是“以 i 位置开始/结束，怎么样怎么样”。我们首先要做的就是确定 dp[i] 表示的是什么，状态转移方程是如何确定dp数组元素之间的推导关系的，接着初始化控制赋值流程，处理边界条件防止越界访问，确定填表顺序和返回值，最后根据思路编写代码。
