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

2. 三步问题

题目描述：小孩每次可以走 1、2 或 3 步，问到达 n 阶台阶有多少种方法？结果对 10^9+7 取模。

分析：

• 状态表示：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
• 注意：需处理 n 较小的情况，且加法时需防止溢出，使用 long long 转换后取模。

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[i] 表示到达第 i 层所需的最小花费。
• 转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
• 初始化：dp[0] = cost[0], dp[1] = cost[1]。
• 返回值：dp[n]（楼顶在数组末尾之后）。

解法二：反向推导

• 状态表示：dp[i] 表示从第 i 阶出发到达楼顶的最小花费。
• 转移方程：dp[i] = cost[i] + min(dp[i+1], dp[i+2])。
• 初始化：dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]。
• 返回值：min(dp[0], dp[1])。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        
        // 初始化前两层
        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[n]
        return min(dp[n - 1], dp[n - 2]);
    }
};

4. 解码方法

题目描述：字符串仅由数字组成，'A'->1, 'B'->2... 'Z'->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，方便处理 dp[2] 依赖 dp[0] 的情况。

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

总结

通过以上练习，我们可以总结出一些通用经验：

1. 状态表示要清晰，通常关注'以 i 结尾'或'以 i 开始'。
2. 边界条件是动规最容易出错的地方，建议多开一位或使用虚拟节点简化逻辑。
3. 空间优化：当只依赖前几个状态时，可用滚动变量将空间复杂度降为 O(1)。
4. 类型安全：涉及累加时注意整数溢出，及时使用 long long 或取模。

掌握这些基础套路，面对更复杂的一维 DP 问题时也能做到心中有数。