解法与正确性

贪心：在每一步，若能跳 2 就优先跳 2；否则跳 1。 理由：两步跳比一步跳更“划算”，且跳 2 不会阻断可达性（题意保证存在解）。若某处能跳 2 却选择跳 1，只会增加一次额外跳跃而不带来任何好处，因此始终优先跳 2 是最优。

复杂度分析

• 时间复杂度：O(n)，每个位置最多检查一次。
• 空间复杂度：O(1)，仅常数额外变量。

题目内容

有一个新的手机游戏，里面有很多不同的云其中一些云是雷云，其他都是积云。

玩家可以跳上任何一个编号与当前云加 $1$ 或 $2$ 相等的积云。而玩家必须避开雷云。请确定从起始位置跳到最后一朵云需要的最小跳数。

假设玩家总是可以赢得游戏。

对于每个游戏，你会得到一个数组，其中编号为 $0$ 的云表示是积云，编号为 $1$ 的云表示需要雷云。

示例：

$c= [0,1,0,0,0,1,0]$ 假设索引从 $0$ 开始。玩家必须避开索引为 $1$ 和 $5$ 的云。

他们可以选择以下两条路径：$0->2->4->6$ 或 $0->2->3->4->6$ 。

第一条路径需要 $3$ 次跳跃或 $0->2->3->4->6$ 。

第一条路径需要 $3$ 次跳跃而第二条路径需要 $4$ 次跳跃。

返回 $3$ 。

输入描述

第一行包含一个整数 $n$ ，表示云的总数。

第二行包含 $n$ 个以空格分隔的二进制整数，描述云 $c[i]$ 的情况，其中 $0<=i<n$ 。

约束条件：

$2 <=n <= 100$

$c[i]$ 取值为 {$0,1$}

$c[0] == c[n-1]== 0$

输出描述

打印赢得游戏所需的最小跳数。

样例1

输入

7
0 0 1 0 0 1 0

输出

4

说明

玩家必须避开 $c[2]$ 和 $c[5]$ 。

游戏最少需要 $4$ 次跳跃。

样例2

输入

6
0 0 0 0 1 0

输出

3

说明

只需要避开 $c[4]$ 。

游戏最少需要 $3$ 次跳跃。