攻克动态规划

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

力扣简单题

题目一:最大子序列和
解题思路:先确定每个位置上的最大子序列和是什么,再把每个位置做比较找出来最大值。
地址: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/
(用贪心算法的时间复杂度更高,但是更好理解。)

全部评论

相关推荐

这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务