总览

解法

记住求过的解来节省时间。

做过的动态规划

最大子序和

(30 分钟)—简单—动态规划

原来这叫做动态规划

爬楼梯

(30 分钟)—简单—动态规划
第一遍选择了回溯，数字超过 30 直接超时。
其实是一条找规律的题，不过可能得看数字规律比较好一些。
斐波那契数列原来有公式啊。可以直接通过公式算也行。不过效率不高

问题抽象的过分了。
斐波那契数列直接的写法原来很差劲，因为每次都要重复计算，动态规划就是记住了之前的路径，好棒啊。
两种方式，一种直接记住上两次的，一个是递归写法，算过的就记住。前一种好一些。

买卖股票的最佳时机

(5 分钟)—简单—动态规划

这一题做第一遍还是比较简单的。

打家劫舍

(8 分钟)—简单—动态规划

不难，知道是动态规划的话，其实就是找当前跟之前结果的关系。原来这就是动态规划。
换成奇偶的法子，如果添加了比较小，就取另一种的最大值更快更强。

###不同路径

(20 分钟)—中等—动态规划

用的自顶向下的规划方法，存了中间计算结果，速度会快一些。
看清楚了题目就是个斐波那契数列而已

换成从底向上的好像更简单了一些。

最小路径和

(15 分钟)—中等—动态规划
方法差不多，趁热打铁还是蛮简单的

其实可以原数组直接存的

解码方法

(15 分钟)—中等—动态规划
逻辑判断有点难，不过还好

三角形最小路径和

(15 分钟)—中等—动态规划
简单的，10 分钟

单词拆分

(20 分钟)—中等—动态规划
第一遍超时了。

换成自顶向下的动态规划简单了一些。

乘积最大子序列

(30 分钟)—中等—动态规划
是比较复杂的动态规划了

写死我了

其实换个思路，少了很多的判断了，就是找到当前位置的最大最小值，遇到负数翻转

完全平方数

(30 分钟)—中等—动态规划
告知了是动态规划，还是不会做，妈的

看下图怎么解！！

计数质数

(15 分钟)—简单—动态规划

一直超时，做了个小优化，就是如果有约束，一定小于他的 sqrt。
其他算法可以看一下是什么样的。
厄拉多塞筛法不错，自己再写了一遍。

粉刷房子

(5 分钟)—简单—动态规划

栅栏涂色

(10 分钟)—简单—动态规划

丑数 II

(30 分钟)—中等—动态规划
我先用了比较容易想到的方法，果然超时了，就是一个一个遍历。
然后看了答案，用的算的方法，很棒的方法，我自己真的想不到，用 3 个指针，指向下次乘的最小值，太优秀了！！

最大正方形

30 分钟—中等—动态规划

这道题目还是蛮难的，主要是规律不好找，正方形是另外 3 个的最小值+1，好玩

最长上升子序列

20 分钟–中等–动态规划

这一题其实想到了就想到了，想不到就不会了。
我用的还算是有问题的解答。

俄罗斯套娃信封问题

15 分钟–困难–动态规划

好难啊，不过其实也能想到的，
先按照 x 排序，如果 x 相同，y 反排，这一步太优秀了！！
然后就是找最长上升子序列。

区域和检索 - 数组不可变

3 分钟–简单–动态规划

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 981909093@qq.com