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

2. 三步问题

题目描述

小孩每次可以走 1、2 或 3 步，求到达 n 阶台阶的方法数。

思路分析

• 状态表示：dp[i] 表示到达第 i 阶的方法数。
• 转移方程：可以从 i-1、i-2、i-3 走过来，故 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
• 初始化：dp[0]=1 (不动), dp[1]=1, dp[2]=2。
• 注意：结果可能很大，需对 10^9+7 取模。

代码实现

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

3. 使用最小花费爬楼梯

题目描述

给定数组 cost，cost[i] 是从该台阶向上爬的费用。一旦支付费用，可爬 1 或 2 步。求到达楼顶的最小花费。

思路分析

• 方法一（自底向上）：
  • dp[i] 表示到达第 i 层的最小花费。
  • dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
  • 注意楼顶在数组末尾之后，需额外处理。
• 方法二（自顶向下）：
  • dp[i] 表示从第 i 层出发到达楼顶的最小花费。
  • dp[i] = cost[i] + min(dp[i+1], dp[i+2])。
  • 填表顺序从右向左。

代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        
        // 初始化前两阶花费为 0（可从 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' 对应 '1'-'26'）。求有多少种解码方式。

思路分析

• 状态表示：dp[i] 表示以 i 结尾的解码方法总数。
• 转移方程：
  1. 单个字符解码：若 s[i] 在 1-9 之间，dp[i] += dp[i-1]。
  2. 两个字符解码：若 s[i-1]s[i] 在 10-26 之间，dp[i] += dp[i-2]。
• 边界处理：使用虚拟节点 dp[0]=1 简化初始化逻辑，避免单独处理第一个字符。

代码实现

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        
        // 虚拟节点初始化
        dp[0] = 1;
        dp[1] = (s[0] != '0') ? 1 : 0;
        
        for (int i = 2; i <= n; i++) {
            // 单个字符判断
            if (s[i - 1] >= '1' && s[i - 1] <= '9') {
                dp[i] += dp[i - 1];
            }
            // 两个字符判断
            int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

总结

掌握一维动态规划的关键在于准确的状态定义和转移方程推导。通过上述四个例题，我们练习了：

1. 基础递推（泰波那契）。
2. 组合计数与取模（三步问题）。
3. 路径优化（最小花费）。
4. 字符串解析与边界技巧（解码方法）。

在实际刷题中，建议先尝试手动推导小数据量的 DP 表，再编写代码验证。遇到复杂边界时，多开一位数组或使用虚拟节点往往是更优解。