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

2. 三步问题

题目描述：小孩每次可以走 1、2 或 3 步，求到达第 n 阶台阶的方法总数。结果需对 10^9+7 取模。

思路分析： 状态 dp[i] 表示到达第 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。由于涉及加法可能溢出，中间计算需强制转换类型并取模。

代码实现：

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

3. 使用最小花费爬楼梯

题目描述：给定一个整数数组 cost，cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦支付费用，你可以选择向上爬一个或者两个台阶。找出达到楼层顶部的最低花费。

思路分析： 这里有两种常见的 DP 定义方式：

1. 自底向上：dp[i] 表示到达第 i 阶的最小花费。dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。注意楼顶在数组末尾之后，所以最终结果是 min(dp[n-1], dp[n-2])。
2. 自顶向下：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 或第 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 的消息通过以下方式进行了编码：'A' -> 1, 'B' -> 2, ..., 'Z' -> 26。给定一个只含数字的非空字符串，计算有多少种解码方法。

思路分析： 这是一个带有条件判断的计数问题。dp[i] 表示以第 i 个字符结尾的解码方法数。

• 如果当前字符 s[i] 非 '0'，则可以单独解码，继承 dp[i-1] 的方案数。
• 如果前两个字符组成的数字在 10~26 之间，则可以组合解码，累加 dp[i-2] 的方案数。
• 若无法解码（如出现 "06"），则方案数为 0。

技巧：为了统一处理边界，可以在 dp 数组前多开一位作为虚拟节点，令 dp[0]=1，这样 dp[2] 的计算可以直接引用 dp[0]，无需特殊判断 i=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) {
            // 单个字符解码
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            // 两个字符组合解码
            int twoDigit = stoi(s.substr(i - 2, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

总结

通过上述四个案例，我们可以看到一维动态规划的通用模式：先定义状态含义，再寻找状态间的递推关系，最后处理好边界和初始化。在实际刷题过程中，不要死记硬背模板，而应多思考'为什么这么定义'以及'如何从子问题推导父问题'。希望这些内容能帮助你建立起扎实的动规思维框架。