网站建设中常见问题分析,大宗商品交易软件哪个好,h5网站开发,珠海网站定制开发一.跳跃游戏类题目简单介绍 跳跃游戏是一种典型的算法题目#xff0c;经常是给定一数组arr#xff0c;从数组的某一位置i出发#xff0c;根据一定的跳跃规则#xff0c;比如从i位置能跳arr[i]步#xff0c;或者小于arr[i]步#xff0c;或者固定步数#xff0c;直到到达某…一.跳跃游戏类题目简单介绍 跳跃游戏是一种典型的算法题目经常是给定一数组arr从数组的某一位置i出发根据一定的跳跃规则比如从i位置能跳arr[i]步或者小于arr[i]步或者固定步数直到到达某一位置可能是数组的最后一个位置也有可能是某一特别的数值处也有可能在这个过程中可能需要求解可能存在的最大值或者最小值。 对于跳跃游戏类的题目经常使用贪心、动态规划、dfs、bfs等方法解决对于可以使用dfs解决的题目经常也可以使用动态规划但一般贪心可以有更好的时间复杂度和空间复杂度。还有经常使用的动态规划剪枝、前缀和、滑动窗口和BFS由于在大部分情况下能用DFS解决的题目都可以用BFS解决且两种方法有基本相同的复杂度尤其是在跳跃游戏这类题目中可以视为一种方法。
二.跳跃游戏类经典题目 在leetcode上有关于跳跃游戏类的题目主要分为两大类一个就是跳跃游戏另外一个是跳跃游戏的衍生比如青蛙酱和跳骚又或者是其他小动物比较经典的题目有
1leetcode70 爬楼梯 2leetcode剑指 Offer 10- II. 青蛙跳台阶问题 3剑指 Offer II 088. 爬楼梯的最少成本 4 leetcode55 跳跃游戏 5leetcode45 跳跃游戏 II 6 leetcode1306 跳跃游戏 III 7leetcode1696 跳跃游戏 VI 8leetcode1871 跳跃游戏 VII 9leetcode1413 逐步求和得到正数的最小值 10leetcode 403 青蛙过河 以上题目都在前三篇中出现过具体的题解不再赘述可参考
跳跃游戏 贪心/动态规划/dfs_跳跃游戏动态规划_ForwardSummer的博客-CSDN博客
跳跃游戏 动态规划剪枝/前缀和/滑动窗口/BFS剪枝_ForwardSummer的博客-CSDN博客
跳跃游戏 DFS-记忆化搜索-动态规划/贪心证明_ForwardSummer的博客-CSDN博客
那么还有一些其他的跳跃游戏类的题目可以进行尝试
1LCP 09 最小跳跃次数 21345 跳跃游戏 IV 31340 跳跃游戏 V 41654 到家的最少跳跃次数 5975 奇偶跳
三.跳跃游戏类题目 解题方法与技巧 在整体上跳跃游戏的题目基本都可以使用DFS解决如果在时间复杂度上不能满足要求那么加上一个记忆化搜索基本可以解决大部分的题目另外还可以进行剪枝在DFS和BFS和动态规划时也经常使用。对于有些题目动态规划反而要比DFS、BFS的方法好理解当明白状态的转移后不用再去具体怎么走边界条件如何反而更容易。 对于可以使用动态规划解决的题目都可以使用DFS来做如果在刚开始不能够很好的推出状态方程不像 leetcode70 爬楼梯 这种可以一眼看出状态转移规律的还是建议先写DFS明确边界条件列举所有可能下一次走的可能路径进行递归注意不要StackOverFlow基本都可以解决问题最多加上剪枝和记忆化搜索。对动规三部曲不熟悉可以看看之前的文章以及左神老师的视频在动态规划推导方程这块讲的还是很不错的。
跳跃游戏 DFS-记忆化搜索-动态规划/贪心证明_ForwardSummer的博客-CSDN博客
Java-算法-动态规划_java动态规划_ForwardSummer的博客-CSDN博客
【一周刷爆LeetCode算法大神左神左程云】 对于有些题目可以使用贪心的思想但此类题目往往不好想且难以证明贪心的正确性需要对题目的敏锐感觉以及大胆的尝试和边界的判断的准确性。
四.跳跃游戏类题目 做题顺序推荐 对于在前三篇的文章已经做过的十道题目接下来做一个顺序推荐。
1leetcode70 爬楼梯动态规划滚动数组优化
2leetcode剑指 Offer 10- II. 青蛙跳台阶问题动态规划整数取值较大的取余操作
3剑指 Offer II 088. 爬楼梯的最少成本动态规划开始出现成本项
4leetcode55 跳跃游戏模拟贪心
5leetcode45 跳跃游戏 II动态规划动态规划剪枝贪心
6leetcode1306 跳跃游戏 IIIDFS
7leetcode1696 跳跃游戏 VI动态规划动态规划剪枝动态规划滑动窗口
8leetcode1413 逐步求和得到正数的最小值动态规划滚动数组
9leetcode1871 跳跃游戏 VII动态规划动态规划前缀和动态规划滑动窗口BFS剪枝
10leetcode 403. 青蛙过河DFS记忆化搜索动态规划
以及其他五题
111654 到家的最少跳跃次数
12975 奇偶跳
131340 跳跃游戏 V
141345 跳跃游戏 IV
15 LCP 09 最小跳跃次数
