友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
Dynamic Programming 动态规划
动态规划的设计思想：「不是直接面对问题求解，而是从一个最小规模的问题开始，新问的最优解均是由比它规模还小的子问题的最优解转换得到，在求解的过程中记录每一步的结果，直至所要求的问题得到解」。
动态规划的五部曲：
-
确定 dp 数组（dp table）以及下标的含义
-
确定递推公式
-
dp 数组如何初始化
-
确定遍历顺序
-
举例推导 dp 数组
.1. 0/1 Knapsack 0/1 背包
.2. Unbounded Knapsack 无限背包
.3. Fibonacci Numbers 斐波那契数列
.4. Palindromic Subsequence 回文子系列
.5. Longest Common Substring 最长子字符串系列
.5.1. 经典题目
Longest Common Substring，最长相同子串
Longest Common Subsequence，最长相同子序列
Minimum Deletions & Insertions to Transform a String into another，字符串变换
Longest Increasing Subsequence，最长上升子序列
Maximum Sum Increasing Subsequence，最长上升子序列和
Shortest Common Super-sequence，最短超级子序列
Minimum Deletions to Make a Sequence Sorted，最少删除变换出子序列
Longest Repeating Subsequence，最长重复子序列
Subsequence Pattern Matching，子序列匹配
Longest Bitonic Subsequence，最长字节子序列
Longest Alternating Subsequence，最长交差变换子序列
Edit Distance，编辑距离
Strings Interleaving，交织字符串
.6. 树形 DP 套路
树形 DP 套路使用前提：如果题目求解目标是 S 规则，则求解释流程可以定成以每一个节点为头节点的子树在 S 规则下的每一个答案，并且最终答案一定就在其中。
树形 DP 套路的解题步骤
-
第一步：以某个节点 X 为头节点的子树中，分析答案有哪些可能性，并且这种分析是以 X 的左子树、X 的右子树和 X 整棵树的角度来考虑可能性的。
请注意这里的顺序：左子树、右子树及整棵树。先左右，如果左右满足，则就可以先上延伸，判断出整棵树。这也是递归调用“触底反弹”的过程。所以，很容易使用递归来完成相关操作。根据上述的流程，使用 后序遍历 更合适。 -
第二步：根据第一步的可能性分析，列出所有需要的信息。比如：最大值、最小值，高度，深度，节点数等等。
-
第三步：合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构。
写出信息结构是把所有的信息都装到一个对象中。如果只需要一个信息，就可以用简单类型来表示了。但是，在树的结构中，大概率是需要多个信息的。 -
第四步：设计递归函数，递归函数是处理以 X 为头节点的情况下的大难，包括设计递归的 base case，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构。