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

2. 三步问题 (Three Steps Problem)

题目链接：LeetCode LCCI 08.09

思路分析： 小孩每次可以走 1、2 或 3 步。到达第 n 阶的方法数等于到达前 3 阶方法数之和。

• 状态表示：dp[i] 表示到达第 i 阶台阶的方法数。
• 转移方程：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. 使用最小花费爬楼梯 (Min Cost Climbing Stairs)

题目链接：LeetCode 746

思路分析： 这道题有两种常见的 DP 视角：

视角一：到达某一层的最小花费

• 状态表示：dp[i] 表示到达第 i 层所需的最小花费。
• 转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
• 初始化：dp[0] = cost[0], dp[1] = cost[1]。
• 返回值：到达楼顶（即最后一层之后），取最后两层的最小值。

视角二：从某一层出发到达楼顶的最小花费

• 状态表示：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();
        // dp[i] 表示到达第 i 层需要的最小花费
        vector<int> dp(n + 1);
        
        // 初始化：前两阶可以直接上，花费即为对应台阶的费用
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for (int i = 2; i <= n; ++i) {
            if (i == n) {
                // 到达楼顶不需要支付额外费用，只需从下两层跳上来
                dp[i] = min(dp[i-1], dp[i-2]);
            } else {
                dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
            }
        }
        return dp[n];
    }
};

4. 解码方法 (Decode Ways)

题目链接：LeetCode 91

思路分析： 这是一个字符串解码问题，涉及边界条件的复杂判断。

• 状态表示：dp[i] 表示以第 i 个字符结尾的解码方法总数。
• 转移方程：
  1. 单个字符解码（1-9）：dp[i] += dp[i-1]
  2. 两个字符组合解码（10-26）：dp[i] += dp[i-2]
• 初始化技巧：为了简化边界处理，可以在 DP 数组前多开一位虚拟节点，设 dp[0] = 1。
• 注意：遇到 '0' 需要特殊处理，不能单独作为有效数字。

代码实现：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        // dp[i] 表示前 i 个字符的解码方法数
        // 多开一位用于处理边界，dp[0] 设为 1 作为虚拟起点
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        
        for (int i = 1; i <= n; ++i) {
            // 单个字符判断
            if (s[i-1] != '0') {
                dp[i] += dp[i-1];
            }
            
            // 两个字符组合判断
            if (i >= 2) {
                int val = (s[i-2] - '0') * 10 + (s[i-1] - '0');
                if (val >= 10 && val <= 26) {
                    dp[i] += dp[i-2];
                }
            }
        }
        
        return dp[n];
    }
};

总结

掌握一维动态规划的关键在于抽象能力。不要死记硬背公式，而是尝试从题目的具体约束中提炼出状态之间的关系。通过大量练习，你会逐渐形成对'状态'和'转移'的直觉，从而能够应对更复杂的二维或多维动态规划问题。