【算法与数据结构】动态规划 - hippowc/hippowc.github.io GitHub Wiki

概念

DP（动态规划，dynamic programming），将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

dp的核心思想：无论是DP还是穷举，我们的算法都是在可能解空间内，寻找最优解。暴力做法是枚举所有的可能解，这是最大的可能解空间。DP是枚举有希望成为答案的解。这个空间比暴力的小得多。一句话总结 -- 尽量缩小可能解空间。

从一个具体场景谈起

假如一个人身上有无数个1，5，10，20，50，100的面钞，如果想要用最少的张数凑够666元，应该如何做？

根据生活经验，从最大的开始拿，因为面值越大用的张数越少嘛，所以6100 + 150 + 110 + 11就可以了。这种策略被称为贪心算法，长期的生活经验表明，贪心策略在大部分时候是对的。

但是如果换一种场景贪心策略也许就会有问题，譬如：身上只有1，5，11三种面值，如果要凑出15元面值，使用贪心策略会产生这样的结果：111 + 14，但实际使用5*3更少。贪心算法的问题在于，它的策略是下一步的解决方案最优，但是局部最优解不是全局最优解。贪心是一种只考虑眼前情况的策略

如何去避免局部最优呢

一个方案是穷举法，将所有可能的情况都列出来，然后在其中去选择最好的情况。穷举法是最笨，也是效率最低的方法，会做很多没有意义的无用功，那么这其中就会有优化的空间。

我们试着从后往前分析这个问题，我们定义f(n)为：要凑出n，需要f(n)张钞票，那么我们上述问题就变为：f(15)=min{f(14),f(10),f(4)} + 1，由此也发现了一个函数关系：f(n)=min(f(n-1), f(n-5), f(n-11)) + 1，已经发现了一个规律，这时候问题变成了，求f(n-1), f(n-5), f(n-11)的最小值的问题。这时，我们发现当n越小的时候求解越简单，所以我们又可以从正向去逐步去获取f(n)的最小值

与穷举法的区别

动态规划舍弃了冗余的信息，譬如我们要计算f(15)，我只需要计算f(14),f(10),f(4)，而不需要其他的。

求出f(n)，只需要知道几个更小的f(c)。我们将求解f(c)称作求解f(n)的“子问题”。

几个概念

无后效性

如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。“未来与过去无关”，这就是无后效性。

最优子结构

大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

之前对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。

应用

应用前提：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

• DAG最短路径
• 最长上升子序列（LIS）：给定一个序列，获取这个序列中最长的递增子序列（不需要连续）
• 背包问题

算法设计

• 把我们面对的状态表示为x。这一步称为设计状态。
• 对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).
• 找出f(x)与哪些状态有关（记为p），写出一个式子（称为状态转移方程），通过f(p)来推出f(x)

以上面凑15钞票，为例子：

• 状态就是 凑15元 钞票，抽象一下，就是凑x元
• 记凑x元需要的张数为f(x)，我们要求出f(15)
• 看f(x)与哪些状态有关：f(x-1) f(x-5) f(x-11) 写出一个方程

前一步叫做设计状态，后一步叫做设计转移；

设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。

后记

所以更优算法的一个常见思维方式是，发现问题中的所有规律，并利用这个规律推导出更一般化的函数表达，其实穷举法也是一种函数，只不过是一个输入对应一个输出的表达方式。

• 每个阶段只有一个状态->递推；
• 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
• 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
• 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。