给定石头的位置列表， 请剖断田鸡能否成功过河（即能否在末了一步跳至末了一个石子上）。 开始时， 田鸡默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。
如果田鸡上一步跳跃了 k 个单位，那么它接下来的跳跃间隔只能选择为 k - 1、k 或 k + 1个单位。 另请把稳，田鸡只能向前方（终点的方向）跳跃。
题目来源：LeetCode 403. Frog Jump
请把稳：
石子的数量 ≥ 2 且 < 1100；每一个石子的位置序号都是一个非负整数，且其 < 2^31；第一个石子的位置永久是0。示例1：
示例2：
题目剖析
月朔看这个题目，觉得挺繁芜，跳跃的限定条件如果上一次跳了k个单位长，下一步只能跳k-1或者k或者k+1个单位长。我们怎么拨开迷雾看到问题的实质呢？
首先，我们考虑如果田鸡当前跳到了位置i，且田鸡跳到位置i时，跳跃的步长是j，此时构成了一个状态，我们记录成dp[i][j]，如果能达到这个状态，则值为1，否则值为0。为什么要这么记录呢？我们思考一下，当前跳到位置i时，肯定是位置i之前的某个位置k，且位置i和位置k的间隔恰好是j。
神奇的事情发生了，我们的问题规模是不是更小了，本来哀求位置i的问题，结果变成求位置k的问题了，且k<i!哈哈哈！
没错，但是想一想，位置k也存在和位置i一样的步长j的问题，还记得那个限定条件吗？那么位置k的步长一定是j-1或者j或者j+1，也便是说我们从dp[k][j']推导到了dp[i][j]，且j' = j-1 or j or j+1，哈哈哈哈！
聪明的粉丝肯定已经知道端倪了。
没错便是他！
状态转移方程
肯定有读者说，得到这个有啥用，彷佛和题目里给出的那些石头位置，没啥关联，且这个k怎么找呢？别焦急，我们给出源码，带着源码一起看，应粉丝的哀求，本次代码是java版本的。
Java
源码剖析：
对付每一个状态dp[i][j]，我们要找到对应的dp[k][j-1]，dp[k][j]，dp[k][j+1]，由于我们知道了当前的位置i，且知道此时的步长是j，那k代表的位置就即是石头位置i的数值减去j得到的数字在石头列表里的位置，这也便是我们的find函数在做的事情！
找到位置k之后，我们只要判断位置k处的状态dp[k][j-1]，dp[k][j]，dp[k][j+1]是否可达，如果可以，显然dp[i][j]也是可达的，由于在位置k，田鸡选择跳j步就到了dp[i][j]的状态！
两层for循环，加一个二分查找，卖力度显然是O(n^2logn)的，由于n<1100，以是繁芜度肯定是可以接管的。空间繁芜度是(n^2)的，也可以接管。
题目总结
本日的这道题目，算法哥给出了一个用动态方案思想办理问题的方法，通过算法哥一系列的动态方案问题的分享，聪明的粉丝是否总结创造了一些办理此类问题的规律，实在动态方案在算法哥这里就一句话“大问题转化成小问题，小问题推导大问题”。大家理解了吗？
实在，这道题目还存在其他的方法可以办理，比如广度优先搜索，递归等，这些就留给读者自己思考吧！
题目分享完毕，麻烦大家动动手指帮算法哥上头条吧，您的关注，点赞，评论，转发，都是对算法哥最大的鼓励！
