攻克动态规划

今天的目标:攻克动态规划

力扣简单题

题目一:最大子序列和
解题思路:先确定每个位置上的最大子序列和是什么,再把每个位置做比较找出来最大值。
地址:https://leetcode-cn.com/problems/maximum-subarray/
同类型题目:
按摩师:https://leetcode-cn.com/problems/the-masseuse-lcci/
打家劫舍(跟按摩师同题):https://leetcode-cn.com/problems/house-robber/

题目二:爬楼梯
解题思路:
1、使用递归(时间复杂度过大)
2、使用递归+记忆数组
3、使用动态规划(相当于斐波那契数列的计算)
地址:https://leetcode-cn.com/problems/climbing-stairs/
同类型题目:
使用最小花费爬楼梯:https://leetcode-cn.com/problems/min-cost-climbing-stairs/
三步问题:https://leetcode-cn.com/problems/three-steps-problem-lcci/
(这里需要注意的是:如果数据过大应该用long然后转int)
斐波那契数:https://leetcode-cn.com/problems/fibonacci-number/
第N个泰波那契数:https://leetcode-cn.com/problems/n-th-tribonacci-number/

题目三:除数博弈
解题思路:
1、通过数学方法归纳,可以直接根据奇偶性得到结果。
2、如果找不到规律,使用动态规划,即找到当前状态和操作完的状态之间的关系:如果能找到操作完后对方必败的情况,则自己必胜。
地址:https://leetcode-cn.com/problems/divisor-game/

题目四:杨辉三角
解题思路:要点是List和ArrayList数据结构的使用。
地址:求所有结果 https://leetcode-cn.com/problems/pascals-triangle/
求单行结果 https://leetcode-cn.com/problems/pascals-triangle-ii/

题目五:买卖股票的最佳时机
解题思路:暴力求解会超时,最简单的办法就是带入实际情况,按照时间的流逝,找当前时间和历史最低点之间的差值。
地址:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

题目六:比特位计数
解题思路:首先分奇偶性,奇数是在前一个偶数的基础上+1,所以奇数的1的个数是前一个偶数的个数+1;因为是二进制,偶数就是在偶数/2的后面加了0,所以偶数跟偶数/2的1的个数应该相同,由此得出算法执行过程。
地址:https://leetcode-cn.com/problems/counting-bits/

题目七:判断子序列
解题思路:使用双指针
地址:https://leetcode-cn.com/problems/is-subsequence/

题目八:获取生成数组中的最大值
解题思路:直接按题目要求写执行过程就行。
地址:https://leetcode-cn.com/problems/get-maximum-in-generated-array/

题目九:传递信息(没理解)
解题思路:深度优先遍历似乎是常用解法,使用动态规划的话,没太弄懂怎么处理的。
地址:https://leetcode-cn.com/problems/chuan-di-xin-xi/

题目十:翻转数位(没理解)
地址:https://leetcode-cn.com/problems/reverse-bits-lcci/

题目十一:下载插件(记住了但是没理解)
地址:https://leetcode-cn.com/problems/Ju9Xwi/

力扣中等题
题目一:最长递增子序列
解题思路:参考解析中的动态模拟过程。
地址:https://leetcode-cn.com/problems/longest-increasing-subsequence/
同类型题目:

题目二:跳跃游戏
解题思路:如果数组长度为1,则当前位置就是最后位置,必然是可达的,因此成为动态规划的临界条件。对于每个位置,判断在它之前可达的位置,加上跳跃距离,是否能达到当前位置。
地址:https://leetcode-cn.com/problems/jump-game/
同类型题目:
跳跃游戏Ⅱ:https://leetcode-cn.com/problems/jump-game-ii/
(用贪心算法的时间复杂度更高,但是更好理解。)

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议