当前位置:>183手游网 > 游戏攻略

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

来源:183手游网 作者: 时间:2023-04-06 13:52:19

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

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

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

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

题目来源:LeetCode 403. Frog Jump

请注意:

石子的数量 ≥ 2 且 < 1100;每块石头的位置序号都是非负整数,而且它 < 2^第一块石头的位置总是0。

示例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),也可以接受。

题目总结

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

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

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

上一篇:梦幻西游网页版秘境降妖副本攻略_梦幻西游秘境降妖攻略 下一篇:沙滩4金币怎么修改?_性感海滩4攻略贴吧

相关推荐

好游推荐

热门游戏