raaaaaar
2021-05-17 23:54:39 +08:00
贪婪，动态规划，分治，都是把一个复杂的问题划分为子问题来解。
贪婪是每个子问题都是最优的，但是最终问题一般不是最优解。
分治的子问题一般是独立的，能够单独求解出来，比如说归并和快排，分成两个子问题排序时，其他子问题是不会影响的。分治的思想就是先分，再治。子问题的类型一般类似，求解方式一样，所以一般用递归，求解完子问题后，再合并求解原问题，比如说二叉树就是一个很常用的分治思想，因为二叉树从定义上来说就是一个递归式的，都能划分为三个节点的子问题，所以很多算法都是差不多的模板。
而动态规划也是把问题划分为子问题，但是在求解的过程中，子问题有些重复出现了，这个时候我们可以时空权衡，也就是空间换时间，把子问题的解记录下来帮助求解，比如说经典的求斐波那契数列，求 f(6)要算 f(5) 和 f(4)，这里要算一边 f(4)，而求 f(5)？时又要求 f(4) 和 f(3)，显然 f(4) 就重复计算了，那么我们就可以提前把结果存下来，以后用的时候直接查找就行了。转换为迭代就是这个思想。
那么一般什么问题适合动态规划呢？
子问题重复：子问题有重复的，这是动态规划优化的原理，当然子问题如果没有重复也可以做，不过就没有意义了。
无后向性：把问题划分为子问题后，通常子问题是一个线性的链，这个链要是一个马尔可夫链，也就是说，后面阶段（子问题）的解，只和现在这个阶段的解有关，而和以前的解无关。比如求 f(6) 时，结果就只和前一个阶段的 f(5) 和 f(4) 有关，而和其他的无关。
最优化原理：和贪婪一个思想，也就是说，每个阶段的解必须是最优的，而且通常需要先证明，最终问题的最优解等价于局部各阶段最优，这个时候才会使用动态规划。
动态规划的实质是什么？
分治+时空权衡解决冗余
那么动态规划应该具体怎么做？
分析问题的结构，看它是不是满足上面的三个原则，或者能转换为类似的问题。比如说，f(6) 能分为 f(4) 和 f(3)，这就是一个阶段，并且阶段有重复的，那么这个问题就能用动态规划来做。一般可以画决策树来帮助理解，也就是说，要解决这个问题，需要解决那些问题？这样一层层的分析下去的一棵树。
递归求解。我们可以从原问题开始一个阶段一个阶段的往下求解，也可以反过来从最低的阶段求解，而在这个过程中，我们通常会发现不同阶段间的转移是有规律的，通常问题的重点就在于如何找到这个状态转移方程。
根据得到的值，求解最优值。
在找转移方程的时候，问题怎么分阶段，每个阶段具体和什么信息有关，又怎么用符号来表示一个阶段，最后才是怎么找出阶段间的关系。通常动态规划中有一种常见的划分阶段的方式，那就是选择还是不选择这样二元的关系。
比如说在组合问题中，要对 n 个数选择 k 个数，我们一个个的选，对于每一个数，就有选或者不选两种可能，如果第一个数选，那么还需要从 n-1 个数里选 k-1 数出来，如果选，那么需要从 n-1 个数里选 k 个数，最终的结果就是这两种情况的和。在这里我们以数的选与不选作为阶段，同时也自然推出了转移方程，最终的结果是和，但是比如背包，或者最短路径中，通常是多个值的最值。