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

代码实现：

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] 是从该台阶向上爬需要支付的费用。你可以从下标 0 或 1 开始，求到达楼顶的最小花费。

思路一：自底向上 定义 dp[i] 为到达第 i 层所需的最小花费。到达楼顶（即超过最后一个元素）需要从倒数第一或倒数第二层跳上来。

思路二：自顶向下 定义 dp[i] 为从第 i 层出发到达楼顶的最小花费。此时填表顺序应从右向左。

代码实现（自底向上）：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        // 初始化前两阶，因为可以从 0 或 1 开始，所以到达这两阶的花费为 0
        // 注意：这里 dp[i] 表示到达第 i 层的最小花费，不包含当前层的 cost
        // 另一种常见定义是 dp[i] 表示到达第 i 层并支付 cost[i] 后的总花费
        // 采用第二种定义更直观：
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for (int i = 2; i < n; i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 最后一步可以直接从 n-1 或 n-2 跳到楼顶，不需要再付楼顶的 cost（因为楼顶没有 cost）
        return min(dp[n - 1], dp[n - 2]);
    }
};

4. 解码方法

给定只包含数字的字符串，将其解码为字母（'A'-'Z' 对应 '1'-'26'），求有多少种解码方式。

关键点：

1. 单个字符必须在 1-9 之间。
2. 两个字符组合必须在 10-26 之间。
3. 遇到 '0' 时需要特殊处理，因为它不能单独解码，必须与前一位结合。

技巧： 为了简化边界判断，可以在 dp 数组中多开一位作为虚拟节点。dp[0]=1 代表空字符串有一种解码方式（基准）。这样在处理 dp[2] 时，可以直接引用 dp[0] 而无需额外判断索引是否越界。

代码实现：

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

总结

掌握动态规划的关键在于熟练运用状态定义和转移方程。在实际编码中，注意以下几点：

• 边界处理：利用虚拟节点或多开空间简化逻辑。
• 数据类型：涉及累加时注意使用 long long 防止溢出。
• 空间优化：如果当前状态仅依赖前几个状态，可使用滚动变量替代数组。
• 调试习惯：手动模拟小数据量的填表过程，验证逻辑是否正确。

通过不断练习上述类型的题目，能够建立起对动规问题的直觉，从而应对更复杂的变体。