题目: 跳跃游戏

分析

动态规划法

贪心法是指在算法的进行过程中，永远以当前最优的方式去尝试全局最优解。

跳跃游戏中尽可能地往远跳，最远可以跳到的位置如果是终点，则可以到达终点，否则无法到达终点。

在跳跃游戏中跳到最远位置，要么是从当前位置往前跳，要么是前序的位置可以跳到最远的距离，所以这是一个最优子结构的问题，可以尝试使用动态规划法解决。

动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤。

• 确定状态和状态变量
  • 分析问题特点，按照时间或者空间特征，将问题分为有序的若干阶段，因为动态规划是按顺序递推求解，所以阶段一定是可排序的。
  • 确定问题每个阶段求解时的状态，确定所需要的变量。求解过程一般是确定dp数组以及下标的含义。

• 确定状态转移方程
  • 分析决策过程，确定状态转移方程，决策和状态转移是相互联系的，状态是根据上一阶段状态以及当前决策变迁到当前状态的，所以确定决策就可以明确状态迁移方程，实际求解过程中，往往根据当前阶段和上一阶段的状态差异，推导决策过程。
• 确定边界条件
  • 状态转移方程是递推的过程，所以需要确定递推的边界条件。因为递推过程是从前到后依次执行的，所以边界条件一般就是初始值。

跳跃游戏的可以使用数组中的每个位置 n 作为变量，f（n）也就是位置 n 最远可以跳到位置。

如果f（n-1）最远可以跳到的位置大于 a_n 的值，说明从位置 n 最远可以跳到 f（n-1）- 1，否则是跳到 nums[n] 的位置。

状态转移方程的边界是 f（0）= 0。