中文名动态规划猛一看不知所云，这就像很多的从英文翻译来的中文科学词汇一样，看得一头雾水，不够直白，就像几何，代数这种概念，对于初学者来说不知道它在讲什么。 但是看了英文词以后就恍然大悟，几何的英文geometry拉丁文的意思就是测量土地，一下子概念就很清晰了。 所以用中文来学科学就经常会遇到这种困难，人为制造的困难。 所以学科学还是要直接看第一手的材料，了解第一手的知识。
DP的变种很多，是算法竞赛的常见题型，一些经典的例子我在这里整理下来，从他们又可以拓展到更多的变种。 算法这东西，自己想的时候经常百思不得其解，但是看了别人的解答以后又经常拍着大腿说这么简单，我怎么想不到。这个现象刘未鹏的博客里讲的比较详细。这里暂时不做讨论。但是勤加练习确实是可以锻炼算法思维，同样也包括数学思维，这就是为什么数学家很多是搞竞赛出身，他们都经过大量的数学训练，把这些基本的数学概念运用的滚瓜烂熟。
用python刷题刷了很久，感觉普通的dp题已经都是秒掉，最近拿java重刷，开始有些吃力，java很多api不是很熟悉。 最近学系统设计遇到一个wordbreak的题，本来是挺简单的题目，但是在lintcode上写的dfs+memo的方法总是通过不了，报stack overtflow。 仔细一琢磨，原来这道题是要求你用bottom-up的方法。 我之前一直没感受到bottom-up和top-down有多大的区别，总以为在时间复杂度和空间复杂度上是一样的，但是在比赛中看到基本所有高手都是写bottom-up不是非常理解，这次终于搞明白了。
- top-down如过递归太深，会有stack overflow的风险
- 两者的时间复杂度和空间复杂度是一样的
- 如果具体的问题不容易剥离出bottom-up的话可以用top-down
- 如果有些问题不需要把所有subproblem全部计算的话，可以用top-down节省资源
- 其余能用bottom-up尽量用bottom-up
这次weekly 190的结果依然不是很理想。 前三题很快水掉。到了第四题1458， 先想的是能不能贪心，先把两个数组各自分成正的和负的两个集合，每次取同样集合中的最大值相乘，依次进行下去知道其中一个集合为空。 不过再一看题目，发现要求subsequence，那么顺序就很重要，所以这种greedy的方法行不通，然后就很快有了dp的思路。 我尝试着想，这个dp应该长这个样子，dp[i][j], 先试试dp[i][j] 其中i和j分别代表num1 和 num2的位置坐标，那么存储的信息是什么呢，试一下i,j分别代表以i，j为起始点一直到数组结尾的两个数组，组成的maximum dot product。然后发现是可行的，就开始思考具体的细节，具体的状态转移方程。 dp[i][j] = max(nums1[x] * nums2[y] + dp[x+1][y+1]), x >=i, y>=j，很简单对吧，然后就开始实现了。 当然里面有一点小边界条件，修修补补，难不到我，很快就把测试样例 给ac了，可是一提交问题来了，TLE，果然！ 然后我开始基于我这个方程去做一些修修补补的优化，考虑到每次需要遍历i->n1, j->n2，我开始想是不是可以直接pass掉其中一部分的判断，然后确实想到了其中两个可以优化的地方。 但是这个i->n1, j->n2的遍历一直存在。 我开始把问题想得更加复杂，我发现了一个 特性，dp[i][j]，固定i或j，是递减的。 然后我开始想是不是可以用young-table去将这个2维的查询缩减到1维，然后发现很难捋出头绪。想着是不是可以用binary search来缩减查找，结果陷入一个死胡同，越走越远。 结果时间一分一秒过去，耗时一个多小时还是没做出来。。。 看了答案，差点气晕过去，转移方程其实可以优化成dp[i][j] = max(nums1[i] * nums2[j] + dp[i+1][j+1], dp[i-1][j], dp[i][j-1])，根本不需要做一个二维的遍历。。。 感觉好蠢。
然后我开始思考，为什么这个看似简单的题目，我最终没有解出来？ 首先这里面用到的知识都是我已知的，没有新知识。 那问题就在于最核心的，为什么没有找到最优的状态转移方程， 而不仅仅是找到状态转移方程。 总结几点。
- 动态规划问题有非常多的变化，并不是考察知识点，而是考察思维方式。这个很锻炼人，我觉得这个需要集中练习一下。
- 不能满足于仅仅找到转移方程，一定要找到最优的转移方程，一般来说肯定要优化到O(n)或者O(nlogn)。
- 在实现算法前还是要分析一下时间复杂度，如果时间复杂度在n2，并且直觉有更简单的方法，那么就不要先着急实现，再尝试一下其他的思路。
- 如果一条路走下去感觉似乎很难找到最优解，可以尝试着倒退到最开始，变换一下最开始的状态定义和状态转移。 这里面其实状态定义是没有问题的，但是状态转移为什么一直没想到 感觉很奇怪。 我一心想着二维去遍历，忘了其实只需要next的数据就可以。以此为戒，以后多加练习动态规划，同时尝试练习正确的思考方式。
https://zhuanlan.zhihu.com/p/62521862
- Maximum Length of Repeated Subarray 貌似一直没有针对练过这个最长公共子串和子序列的问题，总觉得更最长递增是同样道理，可是今天做这一题的时候竟然卡壳了，不知道是不是状态不好，反正只想出来了O(n3)的方法。 思路一直卡着，把dp[i]当公共子串的第一个元素，结果怎么想都觉要比对后面所有元素直到有不同。
结果看了discussion才发现原来这一类dp应该是存储公共子串末尾元素。只是转一个小弯，一下子没转过来。 也没有更多往深入去想，导致这个本该很简单的题目没做出来，记下来作为教训。
https://www.jianshu.com/p/25cc707d9c56
4个月前做过一道tsp的题目，仔细研究理解清楚了，但是不知道那个方法叫做状态压缩。过了4个月再次遇到的时候，一下子没有思路（还是不够熟悉）， 想了一会儿，知道这是tsp，也模糊的记起需要压缩一些状态，但是不是很确定，而且具体操作也一时没有捋清。 今天郑重整理一下这一类问题，同时把状态压缩的概念再强化一下。
首先这类问题还是遵循dp的思路，找到状态转移方程，找到最优子结构，还有无后效性。 只是其中关于状态存储变换这一部分可以进行适当的压缩，其余跟dp没有太大区别。 最后就是如果是需要返回路径的话，需要记录每个节点的前一节点，类似链表的形式。
第一次遇见这个问题是在186的周赛上1425. Constrained Subsequence Sum，当时看完题大概几分钟后有了思路，想出了一个dp解法，但是提交后超时了。 一下子有一点紧张，然后就开始努力想如何优化，因为每次只需要检查前k个dp的值，所以我就想是不是可以用堆来维护最大值。不过这里遇到了一个问题，如果保证 heap里只有前k个元素，这里卡了一会儿，搜了一下，发现可以用一种lazy delete的方法，很巧妙。实现后就AC了。
不过今天正式接触到单调队列862. Shortest Subarray with Sum at Least K， 这里面需要维护subarray的sum，保证大于等于k，我依然是想到了 dp，可是在处理当前dp跟前面的dp值进行合并处理的时候，复杂度恒定在k，不知道该如何优化这一块。然后搜了一下发现有一种单调队列的方法，非常的smart， 保证了时间复杂度在O(n)，非常适合解决这类问题。
然后就回想到上周1425题里面有人用到deque，然后现在发现原来这个就是单调队列优化dp，在dp需要考虑前k个dp值得最大或最小值时，可以结合单调队列的思想， 从而大大降低时间复杂度！
遇到1246题，尝试了半天没找到子问题的划分方法，后来想一想这个是不是属于区间dp的类型。所以专门整理一下区间dp的问题和套路。特意整理四大dp，一一攻克。
这个问题是在滴滴的面试中遇到的，当时大致情况是这样
- 面试官给了个二维方格，求左上角到右下角路径最小和。 我一看这题太简单，就是最基本的dp，刷刷写完了。
- 然后面试官开始放大了，如果是左上到右下之后，再要求返回至左上，且往返路径除了起始点和终点之外不能有重合。
- 然后脑子就开始高速运转，我似乎都听到了风扇的响声。 一开始做了些尝试，先确定第一条路径，然后把矩阵分割成两块，然后 再在分割的区域求第二条路径，但是这样的话需要存储路径，会非常的复杂。陷入沉思
- 放弃分开求两条路径，尝试直接优化这个环路，dp增加一维存储当前步数（考虑到每次移动只能右下，所以步数是有很大信息量的）， 然后区分去路和回路，判断下一步应该是走右下还是左上。 同时判断是否下一步是否被访问。 这个思路猛一看似乎正确，给面试官忽悠 住了。 可是我总觉得这里有问题，因为dfs的时候用vis存储点是否被访问，这个过程意味着会遍历所有可能的路径，显然是不正确的。。。 然后我就老样子，一遍遍地绕着东大校园转，先是捋清了思路，确定这个解法是错的，然后开始想正确的解法。 然后想了半天竟然发现毫无 思绪，曾经某个瞬间，尝试说能不能用两条路线并行去走，但是从未遇到过这种两个点的dp，不知道如何存储状态，也不知道是否可行，就把这个思路个否定了。 结果无论如何也找不到正确方法，回去上网查，竟然都找不到类似的题目。 唯一搜索到的相关的是一个轮廓线的专利算法。。。 我当时心里就mmp，你竟然拿这种难度的题考我？
- 最后实在是想不明白，为什么刷题刷得也不少了，这种题竟然完全没有见过？？？ 实在想不通，决定求hr问一下面试官。 幸亏面试官 很nice，给我发来了详细的正解，看完以后，果然如我所料，这tm是一道NOIP的提高组题，而且这个题目确实是很罕见。。。 我只查到了 中文资料，英文资料上找不到类似的题目。 他最开始的出处在2000年的NOIP提高组，这类题被称作多线程dp，，，我心里千万只草尼马 奔腾。
- 不过庆幸一点，我确实想到了这种思路，但是因为从未遇到过，所以没敢继续往下深入。 看了别人的思路后觉得这一题确实甚是巧妙。 dp果然是变化万千。 提醒自己以后遇到这种感觉是dp的题的时候，应该多往dp方向思考，多想如何分割状态，不要想太诡异的新解法（比 如优化环。。。）