【DP 入门】最小花费爬楼梯

📌 题目描述

有一段共 n 个台阶的楼梯，每个台阶 i 有一个非负花费 cost[i]。 你可以从台阶 0 或台阶 1 出发，每次可以选择 走 1 步 或 ​跨 2 步​，走到某个台阶 i 时需要支付 cost[i] 的花费。

问： 爬到楼顶（台阶 n 的位置）所需的最小花费是多少？ （楼顶位于台阶 n 的上方，不需要额外花费）

✨ 输入格式

• 第一行：一个整数 n，表示台阶数。
• 第二行：n 个整数，表示 cost[0] … cost[n-1]。

数据范围：

1 ≤ n ≤ 10^5
0 ≤ cost[i] ≤ 10^4

📤 输出格式

• 输出一行，一个整数，表示到达楼顶的最小花费。

💡 输入输出样例

样例 1

输入

5
1 100 1 1 1

输出

3

解释 路径选择：

• 从 0 → 1（花费 1）
• 从 1 → 3（跨两步，花费 +1 = 2）
• 从 3 → 5（跨两步，花费 +1 = 3）

样例 2

输入

3
10 15 20

输出

15

解释 路径选择：

• 从 0 → 2（跨两步，花费 15） 比走 0 → 1 → 2 更省。

🔎 题目分析

状态设计 dp[i] 表示到达第 i 个台阶的最小花费。

状态转移

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

$dp[0] = 0, \quad dp[1] = cost[0]$ 答案

$\text{res} = \min(dp[n], dp[n-1]$ )​时间复杂度​ ：O(n) ​空间复杂度​： O(n)，可优化到 O(1)。