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

力扣简单题

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