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

实际运行时，注意 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];
    }
};

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

总结

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