动态规划入门：从泰波那契数到解码方法

在算法学习中，动态规划（Dynamic Programming）是一个核心且重要的知识点。为了让大家更好地掌握它，我们首先梳理一下解决 DP 问题的一般步骤。

一般步骤：

1. 状态表示：创建 DP 表，明确 dp[i] 的含义。
2. 状态转移方程：推导 dp[i] 如何由之前的状态得出。
3. 初始化：确保填表时不越界。
4. 填表顺序：保证计算当前状态时，所需的前置状态已计算完成。
5. 返回结果：根据题目要求和状态定义返回最终值。

接下来，我们通过三个经典例题来具体实践这些步骤。

第 N 个泰波那契数

第 N 个泰波那契数

这道题与斐波那契数列类似，区别在于当前数是前三数之和。我们按照通用步骤分析：

1. 状态表示：dp[i] 表示第 i 个泰波那契数。
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
3. 初始化：由于涉及 i-3，当 i=1 时会越界。根据题目可得：dp[0]=0, dp[1]=1, dp[2]=1。
4. 填表顺序：从前向后依次计算。
5. 返回结果：直接返回 dp[n]。

需要注意边界情况，当 n=0, 1, 2 时直接返回对应值。

class Solution {
public:
    int tribonacci(int n) {
        // 处理边界情况
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        // 创建 dp 表
        vector<int> dp(n + 1);
        
        // 初始化
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        
        // 填表
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        
        // 返回结果
        return dp[n];
    }
};

该解法时间复杂度为 O(N)，空间复杂度为 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;
        int d = 0;
        int count = n - 2;
        
        while (count--) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        
        return d;
    }
};

使用最小花费爬楼梯

使用最小花费爬楼梯

注意：楼顶不是最后一个下标的位置，而是最后一个下标之后的位置。

状态表示方法一

1. 状态表示：dp[i] 表示到达第 i 个台阶的最小花费（以 i 为结尾）。
2. 状态转移方程：可以从 i-1 走一步，或从 i-2 走两步。取较小值： dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
3. 初始化：可以从下标 0 或 1 开始，无需花费。故 dp[0]=0, dp[1]=0。
4. 填表顺序：从前向后。
5. 返回结果：返回 dp[n]。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // 楼顶是最后一个下标后面的那一个位置
        vector<int> dp(n + 1, 0);
        
        // 初始化 dp[0], dp[1] 已默认为 0
        
        // 填表
        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];
    }
};

状态表示方法二

我们也可以定义 dp[i] 为从第 i 个台阶出发到达楼顶的最小花费。

1. 状态表示：dp[i] 是以 i 为起点到达楼顶的最小花费。
2. 状态转移方程： dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])
3. 初始化：dp[n-1] = cost[n-1], dp[n] = 0。
4. 填表顺序：从后向前。
5. 返回结果：起点可能是 0 或 1，返回 min(dp[0], dp[1])。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        
        // 初始化
        dp[n - 1] = cost[n - 1];
        dp[n] = 0;
        
        // 填表
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }
        
        return min(dp[0], dp[1]);
    }
};

解码方法

解码方法

这道题稍微复杂一些，数字需转换为字符（AZ 对应 126），0 无法单独解码，前置 0 如 06 也无法解码。

常规解法

1. 状态表示：dp[i] 表示以 i 位置为结尾的解码方式总数。
2. 状态转移方程：
   • 若 s[i] 可单独解码（非 '0'），则加上 dp[i-1]。
   • 若 s[i-1] 和 s[i] 组合有效（10~26），则加上 dp[i-2]。
3. 初始化：需特殊处理前两个字符的情况。
4. 填表顺序：从前向后。
5. 返回结果：返回 dp[n-1]。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        
        // 初始化
        if (s[0] != '0') dp[0] = 1;
        
        if (n == 1) return dp[0];
        
        if (s[1] != '0') dp[1] += dp[0];
        
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if (t >= 10 && t <= 26) dp[1] += 1;
        
        // 填表
        for (int i = 2; i < n; i++) {
            if (s[i] != '0') dp[i] += dp[i - 1];
            
            int tt = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (tt >= 10 && tt <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n - 1];
    }
};

优化解法

我们可以多开辟一个空间，将初始化逻辑融入循环中，避免重复代码。

1. 多开空间含义：dp[0] 设为 1，作为虚拟起始点，方便处理前两个字符的组合情况。
2. 下标映射：此时 dp[i] 对应字符串 s 的第 i-1 个字符。
3. 返回结果：返回 dp[n]。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        
        if (s[0] != '0') dp[1] += 1;
        
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            
            int tt = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (tt >= 10 && tt <= 26) dp[i] += dp[i - 2];
        }
        
        return dp[n];
    }
};

通过这三个例子，我们可以看到动态规划的核心在于准确的状态定义和转移逻辑。在实际编码中，注意边界条件的处理和空间优化，能让代码更加健壮高效。