动态规划实战：斐波那契变体与经典题目解析

空间优化

观察发现，计算 dp[i] 只需要前三个值。我们可以用滚动变量替代数组，将空间复杂度从 O(n) 降至 O(1)。

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;
        // 初始状态对应 T(0), T(1), T(2)

        for (int i = 3; i <= n; i++) {
            d = 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)
        }
        return d;
    }
};

二、面试题 08.01. 三步问题

题目链接： https://leetcode.cn/problems/three-steps-problem-lcci/

题目解析

计算从 0 到达台阶 n 的不同方法总数。每次可迈 1、2 或 3 步，结果需对 10^9 + 7 取模。

算法原理

状态表示

dp[i] 表示到达第 i 个台阶的方法总数。

状态转移方程

可以从 i-1、i-2 或 i-3 迈一步到达 i： dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD

初始化

• n=1: 1 种方法，dp[1] = 1
• n=2: 2 种方法，dp[2] = 2
• n=3: 4 种方法，dp[3] = 4

代码实现

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 步或 2 步，花费由 cost 数组决定。

算法原理

状态表示

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 层开始，因此起点代价为 0：

• dp[0] = 0
• dp[1] = 0

代码实现

解法一：自底向上填表

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];
    }
};

解法二：从顶层反推

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/

题目解析

给定只包含数字的字符串 s，每个数字代表字母（1='A', ..., 26='Z'）。计算所有可能的解码方案数量。

算法原理

状态表示

dp[i] 表示字符串 s 的前 i 个字符能够解码的方式总数。

状态转移方程

1. 单个字符解码：如果 s[i-1] 不为 '0'，可以独立解码，dp[i] += dp[i-1]。
2. 两个字符解码：如果 s[i-2] 和 s[i-1] 组成的数值在 [10, 26] 范围内，可以合并解码，dp[i] += dp[i-2]。

初始化

• dp[0] = 1：空字符串有 1 种解码方式（作为边界条件）。
• dp[1] = s[0] != '0'：第一个字符不能是 '0'。

代码实现

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];
    }
};

动态规划的核心在于找到状态之间的依赖关系。通过这四个例子，可以看到无论是数值递推还是字符串处理，只要识别出最优子结构和重叠子问题，就能设计出高效的 DP 解法。掌握这些基础模型，有助于应对更复杂的算法挑战。