【普及-提高】最小爬楼梯费用

题目描述

有一段长度为 n 的台阶，每个台阶 i（从 0 开始编号）都有一个代价 cost[i]。

你可以从下标 0 或 1 的台阶开始，每次可以选择爬 一个台阶 或 ​两个台阶​，并支付所到达台阶对应的代价。

请你计算到达台阶顶部（超出最后一个台阶的位置）所需要支付的最小费用。

注意：顶部在下标 n 位置，即比最后一个台阶再高一级。

输入格式

• 第一行输入一个整数 n，表示台阶的数量。
• 第二行输入 n 个整数，依次表示数组 cost[0], cost[1], …, cost[n-1]。

输出格式

输出一个整数，表示到达顶部的最小费用。

样例 1

输入

3
10 15 20

输出

15

解释 最佳方案是从台阶 1 开始：花费 15，然后直接跳到顶部，总花费 15。

样例 2

输入

10
1 100 1 1 1 100 1 1 100 1

输出

6

解释 最佳路线：从下标 0 开始，选择台阶 0 → 2 → 4 → 6 → 7 → 9，总代价 6。

样例 3

输入

7
10 15 30 5 5 10 20

输出

30

解释 一种最优路径是：台阶 1 → 3 → 4 → 6，总代价 30。

数据范围

• 1 ≤ n ≤ 10^5
• 1 ≤ cost[i] ≤ 10^4
• 时间限制：1s
• 空间限制：256MB