C++面试宝典第24题：袋鼠过河

题目

        一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子。每隔一米就有一个桩子，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳得更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米；如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了。给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达，则输出-1。

        输入描述：输入分两行，第一行是数组长度N (1 ≤ N ≤ 10000)，第二行是每一项的值，用空格分隔。

        输出描述：输出最少的跳数，无法到达输出-1。

        示例：

输入：
5
2 0 1 1 1
输出：
4

解析

        在编程竞赛和面试中，袋鼠过河问题是一道富有策略性的动态规划试题。它要求我们对复杂问题进行逻辑分析，并利用动态规划技术来寻找最优解。此题主要考察应聘者对动态规划、贪心策略等的理解，以及对复杂场景的抽象建模能力。

        使用动态规划算法的处理步骤如下。

        1、dp(i)表示跳到第i个桩子的最小跳跃数。

        2、用j表示弹簧的力量&