前言:
此刻各位老铁们对“a星算法过河”可能比较着重,你们都需要了解一些“a星算法过河”的相关知识。那么小编同时在网上汇集了一些关于“a星算法过河””的相关知识,希望小伙伴们能喜欢,朋友们快快来学习一下吧!导读:粉丝反馈算法哥你的更新频率太低了,今天算法哥放弃大好的阳光,再补一个有趣的动态规划题。题目描述
一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石头(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。
给定石头的位置列表, 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格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版本的。
源码分析:
对于每一个状态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)的,也可以接受。
题目总结
今天的这道题目,算法哥给出了一个用动态规划思想解决问题的方法,通过算法哥一系列的动态规划问题的分享,聪明的粉丝是否总结发现了一些解决此类问题的规律,其实动态规划在算法哥这里就一句话“大问题转化成小问题,小问题推导大问题”。大家理解了吗?
其实,这道题目还存在其他的方法可以解决,比如广度优先搜索,递归等,这些就留给读者自己思考吧!
题目分享完毕,麻烦大家动动手指帮算法哥上头条吧,您的关注,点赞,评论,转发,都是对算法哥最大的鼓励!
标签: #a星算法过河