C/C++ 算法入门：一维动态规划基础实战

动态规划基础

动态规划本质上是某种状态的公式加上一个提前计算好值的容器。通过求出当前位置的值并放入容器中供后续使用，从而解决复杂问题。初始值通常是可见的，由此启动整个计算过程。

严格来说：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 状态存储

动规五步法

1. 状态表示：即 dp 表中 dp[i] 的含义，通常结合题目要求分析子问题。
2. 状态转移方程：推导 dp[i] 的具体计算公式，这是最难的一步。
3. 初始化：保证填表时不越界，根据题目设定初始值。
4. 填表顺序：确保计算当前状态时所需的前置状态已计算完成，通常从左向右或从上到下。
5. 返回值：根据题意从 dp 表中提取最终结果。

提示：状态表示通常为'以 i 位置结尾/开头'，dp[i] 通常通过最后一个状态进行分析；初始化通常通过第一个状态进行分析。处理数字字符判断时，建议转换为数字而非直接比较字符，避免边界错误。

实战演练

1. 第 N 个泰波那契数

这道题是典型的线性递推。我们需要求第 n 个泰波那契数，其规律类似于斐波那契数列，但依赖前三个数。

核心逻辑：

• 状态表示：dp[i] 表示第 i 个泰波那契数。
• 转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
• 空间优化：由于只依赖前三个数，可以使用滚动变量代替数组。

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 ret = 0;
        for (int i = 3; i <= n; ++i) {
            ret = a + b + c;
            a = b;
            b = c;
            c = ret;
        }
        return ret;
    }
};

实际运行时，注意 n 较小时直接返回初始值，避免循环无效执行。

2. 三步问题

小孩每次可以走 1、2 或 3 步，问到达 n 阶台阶有多少种方法。

核心逻辑：

• 状态表示：dp[i] 表示到达第 i 阶的方法数。
• 转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
• 关键点：需要取模运算防止整数溢出。

class Solution {
public:
    int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for (int i = 4; i <= n; ++i) {
            dp[i] = ((long long)dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
        }
        return dp[n];
    }
};

这里使用了 long long 强制转换来避免加法过程中的中间溢出，最后再取模。

3. 使用最小花费爬楼梯

每个台阶都有对应的花费，可以从下标 0 或 1 开始，每次向上爬 1 或 2 步，求到达楼顶的最小花费。

核心逻辑：

• 状态表示：dp[i] 表示到达第 i 层的最小花费。
• 转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
• 注意：楼顶在数组末尾之后，所以 dp 数组长度需为 size+1。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        
        // 初始化：从 0 或 1 开始不需要花费
        dp[0] = 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];
    }
};

另一种思路是从后往前推，从楼顶倒推回地面，逻辑类似，可根据习惯选择。

4. 解码方法

给定一串数字字符串，将其解码为字母（A-Z），求有多少种解码方式。

核心逻辑：

• 状态表示：dp[i] 表示前 i 个字符的解码方法数。
• 转移方程：
  1. 单个字符有效（1-9）：dp[i] += dp[i-1]
  2. 两个字符组合有效（10-26）：dp[i] += dp[i-2]
• 边界处理：多开一位虚拟节点 dp[0]=1，简化 dp[1] 的计算。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0') return 0;
        
        vector<int> dp(n + 1);
        dp[0] = 1; // 虚拟节点
        dp[1] = 1;
        
        for (int i = 2; i <= n; ++i) {
            int oneChar = s[i - 1] - '0';
            int twoChar = (s[i - 2] - '0') * 10 + oneChar;
            
            if (oneChar >= 1 && oneChar <= 9) {
                dp[i] += dp[i - 1];
            }
            if (twoChar >= 10 && twoChar <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

对于需要判断多位数字的情况，不要偷懒直接用字符比较，务必转换为数值后再进行范围判断，这样更稳健。

总结

通过以上四个案例，我们梳理了一维动态规划的通用解题框架。关键在于准确的状态定义和合理的转移方程推导。在实际编码中，注意边界条件的处理和空间复杂度优化，能让代码更高效且易于维护。