小青蛙过河游戏_青蛙过河十只攻略

导读:粉丝反馈算法哥，你更新频率太低。今天算法哥放弃了美好的阳光，补充了一个有趣的动态规划题。题目描述

青蛙想过河。 假设河流等分 x 单元格，每个单元格都可能有一块石头(也可能没有)。 青蛙可以跳上石头，但不能跳进水里。

给定石的位置列表， 请确定青蛙是否能成功过河(即在最后一步跳到最后一块石头)。 开始时， 青蛙默认站在第一块石头上，可以假设第一步只能跳一个单位(即只能从单元格1跳到单元格2)。

如果青蛙跳上一步， k 单位，其下一个跳跃距离只能选择为 k - 1、k 或 k 1个单位。 请注意，青蛙只能跳到前面(终点)。

题目来源：LeetCode 403. Frog Jump

请注意：

示例1：

示例2：

第一天看这个话题感觉很复杂。如果上次跳k单位长，下一步只能跳k-1或者k或者k 一个单位长。如何摆脱迷雾，看到问题的本质？

首先，我们认为，如果青蛙跳到现在的位置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 哈哈哈哈！聪明的粉丝一定已经知道端倪了。

没错就是他！

状态转移方程

一定有读者说得到这个有什么用？似乎与标题中给出的石头位置无关。如何找到这个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)的，因为n<1100，所以复杂性肯定是可以接受的。空间复杂性是(n^2)，也可以接受。

在今天的问题上，算法哥给出了一种用动态规划思想解决问题的方法。通过分享算法哥的一系列动态规划问题，聪明的粉丝是否总结并发现了一些解决这些问题的规则？事实上，动态规划在算法哥这里有一句话：大问题转化为小问题，小问题推导大问题。你明白吗？

事实上，还有其他方法可以解决这个问题，比如广度优先搜索、递归等，让读者自己思考吧！

分享完题目后，请用手指帮助算法哥上头条。你的关注、喜欢、评论和转发是对算法哥最大的鼓励！