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

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

动态规划核心思路

动态规划（DP）本质上是某种状态的公式加上提前求好值的容器。通过计算当前位置的值并存储到容器中供后续使用，从而避免重复计算。

严格来说，动态规划包含四个要素：

• 状态定义：明确 dp[i] 的含义。
• 状态转移方程：推导 dp[i] 与之前状态的关系。
• 初始条件：确定边界值。
• 状态存储：通常使用数组或滚动变量。

解题五步法

在实际刷题中，建议遵循以下流程：

1. 状态表示：确定 dp 表中每个元素的含义。通常以'以 i 位置结尾'或'以 i 位置开始'为切入点。
2. 状态转移方程：这是最难的一步，需结合题目含义推导 dp[i] = ?。
3. 初始化：确保填表时不越界，根据题目要求设定初始值。
4. 填表顺序：保证计算当前状态时，依赖的前置状态已计算完成（通常从左向右或从上到下）。
5. 返回值：根据题意从 dp 表中提取最终结果。

提示：状态表示常涉及'以 i 位置结尾/开头'。初始化通常分析第一个状态，而返回值分析最后一个状态。处理数字字符判断时，务必转换为数值而非直接比较字符，以免出现不可控情况。必要时可开辟额外空间处理边界问题。

---

实战演练

下面通过四道经典题目，逐步应用上述步骤。

1. 第 N 个泰波那契数

题目描述：T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3)。

分析：

• 状态表示：dp[i] 表示第 i 个泰波那契数。
• 转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
• 初始化：dp[0]=0, dp[1]=1, dp[2]=1。
• 填表顺序：从左向右。
• 返回值：dp[n]。

空间优化：由于只需要前三个状态，可以使用三个变量代替数组。

class Solution {
public:
    int tribonacci(int n) {
        // 空间优化写法
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        int a = 0, b = 1, c = 1;
        int ret = 0;
        for (int i = 3; i <= n; i++) {
            ret = a + b + c;
            a = b;
            b = c;
            c = ret;
        }
        return ret;
    }
};

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 问题时也能做到心中有数。