动态规划经典题型：斐波那契数列及变种应用

4. 空间优化

利用滚动变量将空间复杂度从 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;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

二、面试题 08.01. 三步问题

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

1. 题目解析

计算通过步数 1、2 和 3 从 0 到达台阶 n 的所有不同方法总数。答案需对 10^9 + 7 取模。

2. 算法原理

• 状态表示：dp[i] 表示到达第 i 个台阶的方法总数。
• 状态转移方程：dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD。
• 初始化：dp[1]=1, dp[2]=2, dp[3]=4。
• 返回值：返回 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] 表示到达台阶 i 所需的最小花费。
• 状态转移方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
• 初始化：dp[0]=0, dp[1]=0（可从第 0 层或第 1 层开始）。
• 返回值：返回 dp[n]。

3. 代码实现

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

四、91. 解码方法

题目链接： https://leetcode.cn/problems/decode-ways/description/

1. 题目解析

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

2. 算法原理

• 状态表示：dp[i] 表示字符串 s 的前 i 个字符能够解码的方式总数。
• 状态转移方程：
  • 单个字符解码：若 s[i-1] != '0'，则 dp[i] += dp[i-1]。
  • 两个字符解码：若前两位组成的数值在 [10, 26] 范围内，则 dp[i] += dp[i-2]。
• 初始化：dp[0]=1，dp[1] = (s[0] != '0')。
• 返回值：返回 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';
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};

结语

本文通过对斐波那契数列及其变种问题的动态规划求解分析，展示了该算法在减少冗余计算、提升效率上的优势。相比于递归方法，动态规划在时间和空间复杂度上表现更优，且易于扩展至其他问题。