题目描述

一只青蛙想要过河。假定河流被等分为x个单元格，并且在每一个单元格内都有可能放有一石头（也有可能没有）。青蛙可以跳上石头，但是不可以跳入水中。

给定石头的位置列表，请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。开始时，青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。

如果青蛙上一步跳跃了k个单位，那么它接下来的跳跃距离只能选择为k-1、k或k+1个单位。另请注意，青蛙只能向前方（终点的方向）跳跃。

请注意：

石子的数量≥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的问题了，且ki!哈哈哈！没错，但是想一想，位置k也存在和位置i一样的步长j的问题，还记得那个限制条件吗？那么位置k的步长必然是j-1或者j或者j+1，也就是说我们从dp[k][j']推导到了dp[i][j]，且j'=j-1orjorj+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^2*logn)的，因为n1100，所以复杂度肯定是可以接受的。空间复杂度是(n^2)的，也可以接受。

题目总结

今天的这道题目，算法哥给出了一个用动态规划思想解决问题的方法，通过算法哥一系列的动态规划问题的分享，聪明的粉丝是否总结发现了一些解决此类问题的规律，其实动态规划在算法哥这里就一句话“大问题转化成小问题，小问题推导大问题”。大家理解了吗？

其实，这道题目还存在其他的方法可以解决，比如广度优先搜索，递归等，这些就留给读者自己思考吧！