爬楼梯的最小花费

题目描述

给你一个整数数组 cost，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

输入格式

第一行包含一个整数 $n$，表示楼梯的台阶数。

第二行包含 $n$ 个整数，表示数组 cost，其中第 $i$ 个数表示 cost[i-1] 的值。

输出格式

输出一行一个整数，表示到达楼梯顶部的最低花费。

输入输出样例 #1

输入 #1

3
10 15 20

输出 #1

15

样例 #1 解释

你将从下标为 1 的台阶开始，支付 15 的费用，然后向上爬两个台阶到达楼梯顶部。

输入输出样例 #2

输入 #2

5
1 100 1 1 1

输出 #2

3

样例 #2 解释

最优路径是：从下标为 0 开始，支付 1 → 爬两个台阶到下标 2 → 支付 1 → 爬两个台阶到达楼梯顶部。总花费为 1+1 = 2。

数据范围

对于 $100\%$ 的数据，保证 $2 \leq n \leq 1000$，$0 \leq cost[i] \leq 999$。