动态规划

解决动态规划（Dynamic Programming, DP）问题，就像是拼拼图：你不能直接看到全貌，但可以通过组合已经拼好的小板块来构建大图。

该问题特征识别: 状态转移方程, 最优子结构

通常我们可以遵循“DP 四部曲”来攻克任何一道动规题：

1. 确定 DP 数组及其下标的含义

这是最关键的一步。你需要明确 $dp[i]$ 到底代表什么？ 即怎么用数据模型描述

• 在“爬楼梯”中，$dp[i]$ 表示：到达第 $i$ 层台阶所花费的最小体力值。
• 如果不清楚含义，后面的递推公式就会逻辑混乱。

2. 确定状态转移方程

也就是“找关系”。思考：要到达 $dp[i]$，前一步可能在哪里？

• 因为你每次只能走 1 步或 2 步，所以要到达第 $i$ 层，只能从第 $i-1$ 层或第 $i-2$ 层跨上来。
• 为了取最小花费，方程就是：

$$dp[i] = \min(dp[i-1], dp[i-2]) + cost[i]$$

3. 初始化 DP 数组

DP 是靠推导出来的，所以必须有“第一块砖”。

• 根据题意，你可以从索引 0 或 1 开始，且不消耗体力。
• 初始化：$dp[0] = cost[0]$, $dp[1] = cost[1]$。
• 注意： 如果初始化错了，后面的结果会像多米诺骨牌一样全线崩塌。

4. 确定遍历顺序

从前往后还是从后往前？

• 对于楼梯问题，由于 $dp[i]$ 依赖于 $dp[i-1]$ 和 $dp[i-2]$，所以必须从左到右遍历。

总结：从“记忆化”到“空间优化”

当你写出基础的代码后，可以尝试更高级的思考：