本文通过动态规划方法解决了四个经典算法问题：第 N 个泰波那契数、三步问题、最小花费爬楼梯和解码方法。详细阐述了状态定义、转移方程、初始化及填表顺序，并展示了空间优化技巧。代码使用 C++ 实现，涵盖递归转迭代及滚动数组优化，适用于算法学习与面试准备。
斐波那契数列是数学领域中一个经典的问题，在计算机科学中也有广泛的应用。从简单的递归算法到优化的动态规划方法，斐波那契数列的求解体现了算法设计和性能优化的精髓。本文将以动态规划为核心，系统地探讨如何高效地计算斐波那契数列，分析不同方法的时间与空间复杂度，并展示动态规划的强大之处。
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 数。
设 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 数。
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];
}
};
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)。n 的数组来存储所有状态。每次计算 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)
这道题的目标是计算可以通过步数 1、2 和 3 从 0 到达台阶 n 的所有不同方法的总数。
每次可以选择迈 1 步、2 步或 3 步，并且答案需要对 10^9 + 7 取模。
定义一个数组 dp[i]，表示到达第 i 个台阶的方法总数。
dp[i] 包括从 i−1、i−2、或 i−3 的台阶迈一步到达的所有方案数。状态转移公式为：
dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD
这里的取模操作是为了防止结果过大，确保结果保持在 10^9 + 7 的范围内。
根据题目条件：
dp[1] = 1；dp[2] = 2；dp[3] = 4。从小到大依次计算 dp[4] 到 dp[n]，通过累加前 3 项得到结果。
最终返回 dp[n] 即可。
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];
}
};
这道题的目标是计算从数组开头或第二个元素出发，到达数组末尾所需的最小花费。
每次可以迈 1 步或 2 步，花费由数组 cost 决定，其中每个位置的值代表站在对应台阶上的代价。
定义一个数组 dp[i]：
dp[i] 表示到达台阶 i 所需的最小花费。我们可以从前一层 (i−1) 或前两层 (i−2) 迈步到 i，取最小值作为最优解：
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]，即为到达顶部所需的最小花费。
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]);
}
};
本题要求解码一个只包含数字的字符串 s，其中每个数字代表字母表中的字母（1 对应 'A'，2 对应 'B'，…，26 对应 'Z'）。
我们的任务是计算出所有可能的解码方案的数量。
定义一个数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符能够解码的方式总数。
两个字符解码：
如果前两个字符组成的数值在 [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];
单个字符解码：
如果当前位置的字符 s[i-1] 是有效的（即不等于 '0'），它可以独立解码为一个字母。
因此，dp[i] 可以由 dp[i-1] 转移而来：
if(s[i-1]!='0') dp[i] += dp[i-1];
dp[0] = 1：表示空字符串有 1 种解码方法。dp[1] = s[0] != '0'：如果第一个字符不为 '0'，则有 1 种解码方法，否则没有解码方法。从 i = 2 开始填表，一直到 i = n，逐步计算每个 dp[i] 的值。
最终返回 dp[n]，即为整个字符串的解码方法数量。
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];
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online