文章目录
前言
斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。希望通过本研究，为算法设计爱好者提供启发，并在实际问题中应用该技术。
🌞一、1137. 第 N 个泰波那契数
题目链接：https://leetcode.cn/problems/n-th-tribonacci-number/description/
🌜1. 题目解析
Tribonacci 数列是一个递归数列，类似于斐波那契数列，但它的递推公式是：
- 递推公式：
T(n) = T(n-1) + T(n-2) + T(n-3)，对于n >= 3； - 初始条件：
T(0) = 0T(1) = 1T(2) = 1
需要实现一个函数 tribonacci(int n)，返回第 n 个 Tribonacci 数。
🌜2. 讲解算法原理
状态表示
设 dp[i] 表示第 i 个 Tribonacci 数，即前 i 个数的第三阶斐波那契数列。换句话说，dp[i] 是定义如下的递推关系：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3。
状态转移方程
根据题目描述，Tribonacci 数列满足：
dp[0] = 0dp[1] = 1dp[2] = 1dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，对于i >= 3
初始化
初始化初始条件，保证在填写表格的时候不会越界：
dp[0] = 0dp[1] = 1dp[2] = 1
填表顺序
从 i = 3 开始递推填表，因为计算 dp[i] 时，需要依赖 dp[i-1], dp[i-2], 和 dp[i-3] 的值，这些值在计算当前状态时必须已知。因此：
- 填写顺序是从
i = 3开始递增。
返回值
最后返回 dp[n]，即第 n 个 Tribonacci 数。
🌜3. 编写代码
class Solution {
public:
int tribonacci(int n) {
// 3. 初始化（初始条件）
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
// 1. 状态表示：dp[i] 表示第 i 个 Tribonacci 数
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = dp[2] = 1;
// 4. 填表顺序：从 i = 3 到 n
for(int i = 3; i <= n; i++){
// 2. 状态转移方程
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
// 5. 返回值：第 n 个 Tribonacci 数
return dp[n];
}
};
🌜4. 空间优化
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; // 初始状态
for (int i = 3; i <= n; i++) {
d = a + b + c; // 当前状态依赖于前三个状态
a = b; // 滚动更新
b = c;
c = d;
}
return d; // 返回第 n 项
};
-
状态转移方程：
T(n) = T(n-1) + T(n-2) + T(n-3)。- 每次计算当前值
T(n)只需要T(n-1)、T(n-2)和T(n-3)。
-
滚动更新变量：
-
变量
a、b、c分别存储T(n-3)、T(n-2)和T(n-1)。 -
每次计算 d = a + b + c 后，将 a、b、c 滚动更新为下一轮所需的值：
a = b; // T(n-2) 成为 T(n-3) b = c; // T(n-1) 成为 T(n-2) c = d; // T(n) 成为 T(n-1)
-
-
减少空间复杂度：
-
原本需要一个大小为
n的数组来存储所有状态。 -
滚动数组通过动态更新变量，将空间复杂度从 O(n) 优化为 O(1)。
-
🌞二、面试题 08.01. 三步问题
题目链接：https://leetcode.cn/problems/three-steps-problem-lcci/
🌜1. 题目解析
这道题的目标是计算可以通过步数 1、2 和 3 从 0 到达台阶 n 的所有不同方法的总数。
每次可以选择迈 1 步、2 步或 3 步，并且答案需要对 1 0 9 + 7 10^9 + 7 109+7 取模。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp[i]，表示到达第 i 个台阶的方法总数。
dp[i]包括从i−1、i−2、或i−3的台阶迈一步到达的所有方案数。
状态转移方程
状态转移公式为：
d p [ i ] = ( d p [ i − 1 ] + d p [ i − 2 ] + d p [ i − 3 ] ) % M O D dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) \% MOD dp[i]=(dp[i−1]+dp[i−2]+dp[i−3])%MOD
这里的取模操作是为了防止结果过大，确保结果保持在 1 0 9 + 7 10^9 + 7 109+7 的范围内。
初始化
根据题目条件：
- 如果 n = 1，只有 1 种方法，初始化
dp[1] = 1； - 如果 n = 2，有 2 种方法，初始化
dp[2] = 2； - 如果 n = 3，有 4 种方法，初始化
dp[3] = 4。
填表顺序
从小到大依次计算 dp[4] 到 dp[n]，通过累加前 3 项得到结果。
返回值
最终返回 dp[n] 即可。
🌜3. 编写代码
class Solution {
public:
int waysToStep(int n) {
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
const int MOD = 1e9 + 7;
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];
}
};
🌞三、746. 使用最小花费爬楼梯
题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
🌜1. 题目解析
这道题的目标是计算从数组开头或第二个元素出发，到达数组末尾所需的最小花费。
每次可以迈 1 步或 2 步，花费由数组 cost 决定，其中每个位置的值代表站在对应台阶上的代价。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp[i]：
dp[i]表示到达台阶i所需的最小花费。
状态转移方程
我们可以从前一层（i−1）或前两层（i−2）迈步到 i，取最小值作为最优解：
d p [ i ] = min ( d p [ i − 1 ] + c o s t [ i − 1 ] , d p [ i − 2 ] + c o s t [ i − 2 ] ) dp[i] = \min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
初始化
因为可以从第 0 层或第 1 层开始：
dp[0] = 0：从起点出发，不需要额外代价。dp[1] = 0：从起点开始直接跳到第 1 层，也没有代价。
填表顺序
从小到大计算 dp[i]，直至 dp[n] ，其中 n 是楼梯台阶数。
返回值
最终返回 dp[n]，即为到达顶部所需的最小花费。
🌜3. 编写代码
1. 解法一：自底向上填表
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];
}
};
2. 解法二：从顶层反推
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. 解码方法
题目链接：https://leetcode.cn/problems/decode-ways/description/
🌜1. 题目解析
本题要求解码一个只包含数字的字符串 s，其中每个数字代表字母表中的字母（1 对应 ‘A’，2 对应 ‘B’，…，26 对应 ‘Z’）。
我们的任务是计算出所有可能的解码方案的数量。
🌜2. 讲解算法原理
状态表示
定义一个数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能够解码的方式总数。
状态转移方程
-
单个字符解码：
如果当前位置的字符s[i-1]是有效的（即不等于 ‘0’），它可以独立解码为一个字母。
因此，dp[i]可以由dp[i-1]转移而来：if (s[i-1] != '0') dp[i] += dp[i-1]; -
两个字符解码：
如果前两个字符组成的数值在 [10, 26] 范围内，那么它们可以合并解码成一个字母。例如，s[i-2]和s[i-1]组合形成一个数，如果这个数在 [10, 26] 内，则可以由dp[i-2]转移：int t = (s[i-2] - '0') * 10 + (s[i-1] - '0'); if (t >= 10 && t <= 26) dp[i] += dp[i-2];
初始化
dp[0] = 1：表示空字符串有 1 种解码方法。
dp[1] = s[0] != '0'：如果第一个字符不为 ‘0’，则有 1 种解码方法，否则没有解码方法。
填表顺序
从 i = 2 开始填表，一直到 i = n，逐步计算每个 dp[i] 的值。
返回值
最终返回 dp[n]，即为整个字符串的解码方法数量。
🌜3. 编写代码
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp(n + 1);
dp[0] = 1; // 保证后面的填表是正确的
dp[1] = s[0] != '0'; // 第一个字符不能是 '0'
for(int i = 2; i <= n; i++){
// 如果当前字符不是 '0'，可以单独解码
if(s[i - 1] != '0') dp[i] += dp[i - 1];
// 如果当前和前一个字符组成的数字在 10 到 26 之间，也可以解码
int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}
};
结语
本文通过对斐波那契数列的动态规划求解方法的分析与优化，展现了动态规划在减少冗余计算、提升算法效率上的显著优势。相比于递归方法，动态规划在时间复杂度和空间复杂度上均有更优的表现，同时也更易扩展到其他问题。斐波那契数列作为算法入门的重要实例，其研究不仅有助于理解动态规划的基本原理，更能为解决更复杂的现实问题奠定基础。未来，动态规划仍将在算法设计领域发挥重要作用，我们也期待更多优化和创新的出现。
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！