#616. 探险家的跳跃计划
探险家的跳跃计划
探险家的跳跃计划
故事背景
一位探险家正在穿越一片由浮岛组成的海域。浮岛排成了一条直线,每座浮岛上都写着一个非负整数,表示从这座浮岛出发,最多可以向前跳跃多少步。
探险家从第 1 座浮岛出发(下标从 1 开始编号),每次可以选择向前跳 1 步、2 步,直到当前浮岛写明的最大步数为止。探险家想知道,自己是否有办法跳到最后一座浮岛上。
题目描述
给定一个长度为 的非负整数数组,其中第 个元素表示从位置 最多可以向前跳跃的步数。你一开始位于下标为 1 的位置(即数组的第一个元素处)。
每次跳跃,你可以选择向前移动 1 到当前允许的最大步数之间的任意整数步。判断是否存在一种跳跃方式,使你能够到达最后一个位置。
输入格式
- 第一行包含一个整数 ,表示浮岛的数量。
- 第二行包含 个非负整数,第 个数表示从第 座浮岛最多可以向前跳跃的步数。
输出格式
- 如果可以到达最后一座浮岛,输出
YES; - 否则输出
NO。
输入输出样例 #1
输入 #1
5
2 3 1 1 4
输出 #1
YES
样例解释 #1
一种可行跳法是:从位置 1 跳到位置 2,再从位置 2 跳到位置 5。
输入输出样例 #2
输入 #2
5
3 2 1 0 4
输出 #2
NO
样例解释 #2
无论如何,都无法跳过位置 4 处的“0”,因此到达不了最后一座浮岛。
说明/提示
- 对于所有测试数据,保证 。
- 数组中的元素为不超过 的非负整数。