LeetCode-python 403.青蛙过河

题目链接

难度：困难       类型： 数组、动态规划

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

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

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

请注意：

石子的数量 ≥ 2 且 <1100；

每一个石子的位置序号都是一个非负整数，且其 <231；

第一个石子的位置永远是0。

示例1

示例2

dp[stones[i]]表示在第i个石头上可以向前跳的步长的集合

跳到第i个石头时，用当前能跳的步长往前跳，若能跳到石头上，则该石头的步长集合中添加该步长，若最后一块石头的步长集合不为空，则返回True，反之为False

本文链接： https://www.jianshu.com/p/037cc624e3c1

1、首先游戏的目的是要两边的青蛙跳到对岸去。

2、其次青蛙可以向前跳一格，左排前面的青蛙先向前跳一格。

3、最后青蛙也可以跳跃过紧挨的青蛙到下一格上，右排的跳跃过就可以了。

---