动态规划详解一

概述

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

此为wiki百科中的定义，重点是分解

换句话说，就是：

1. 将一个大问题，拆分成几个小问题

2. 求小问题的解

3. 推出大问题的解

以上还有个隐含的条件，即被分解的小问题要和大问题有联系，这样才能从小问题的解推出大问题的解

样例

背包问题

有N件物品和一个容量是V的背包。每件物品只能使用一次。

第i件物品的体积是v[i]，价值是w[i]。

求解在背包容量范围内，所能装物品的最大价值是多少

初步尝试

用最直观的想法来解决此问题，比较容易想到的是：

1. 先装单位价值最高的
2. 再继续装剩下的物品中，单位价值最高的

咦，看起来我把问题分解了

假设第k件物品是单位价值最高的，那只需要解决

有N-1件物品（除了第k件）和一个容量为V-v[k]的背包。。。。

被分解的问题又可以以同样的方式进一步分解，分解的过程中N和V越来越小

若N=1或V<=0，也就有了唯一解

这样我们做到了之前所说的：第一步问题拆分和第二步求小问题的解

第三步是不是也可以做到了？

看起来很简单，把所有小问题的解串起来就可以了

我们找个简单的数算一下

N = 3
V = 5
v = [1,2,3]
w = [2,4,4]

很容易看出，第1、2个物品单位价值最高，都是2，剩余第3个为4/3

根据之前的思路

1. 前两个单位价值一样，但第二个总价更高，所以我们先装第2个；

2. 其次装第1个，其单位价值也是最高的；

3. 此时，价值为2+4=6，已用容量为1+2=3，剩余容量2

4. 再然后，发现剩余的那个已经装不进了

好像不对啊

如果装2和3的话，价值为4+4=8，总价值更大

问题出在什么地方？

我们装了单位价值较高的第1个，但是因为装了它，单位价值较低但总价较高的3装不进去了，如果不装它，反而恰好可以装进去

因小失大，为了1，丢了3

鼠目寸光，为了眼前的利益，放弃了后续可能的更高价值

以上，为贪心

再次尝试

那如何避免因鼠目寸光造成的因小失大呢？我确实也是根据说明先拆分问题再求解再推大问题的呀

因为之前只顾眼前，有问题，所以现在在选择时还需要进一步看一下做的本次选择对后续的影响

比如现在随便选择一个装进背包

若选的是第1个，则后续子问题就变成了

N = N - 1 = 2
V = V - 1 = 4
v = [x, 2, 3]
w = [x, 4, 4]

整个问题的解则为2 + 子问题的解

若选的是第2个，则后续子问题就变成了

N = N - 1 = 2
V = V - 2 = 3
v = [x, x, 3]
w = [x, x, 4]

注意，这里物品1也被拿掉了，相当于1没选，因为先拿2再拿1和先拿1再拿2是一样的，而后者会被选1的那种可能覆盖到，这里无需重复计算

整个问题的解则为4 + 子问题的解

若选的是第3个，则后续子问题就变成了

N = N - 1 = 2
V = V - 3 = 2
v = [x, x, x]
w = [x, x, x]

整个问题的解则为4 + 子问题的解

而这时，子问题中的物品已经没有了，结果肯定是0，无需继续拆了

由于不同的选择，产生的后续子问题也不一样，所以我们无法确定当前选择在后续看来是不是最优的

但我们可以确定，最优解在这三种选择中的一个（废话，所有可能的选择都被你暴力的一个个全列出来了-_-!）

且若每个子问题的解是最优的，那本次最优的选择为

max(2 + 子问题1的解, 4 + 子问题2的解, 4 + 子问题3的解)

没有其他可能了

到目前为止，我们前进了一小步

我们把这个大问题，拆成了3个小问题，并能确保能够从小问题的解得出大问题的解

虽然数量多了，但是问题简单了

同样

我们可以把3个小问题，用同样的方式，继续拆分

这样问题更多了，问题也更简单了

直到物品没了或背包满了，无需继续拆分为止

子问题求解后，上一级问题的解就显而易见了，一直到最上层

以上，我们解决了整个问题

这种方式叫。。。暴力，暴力的递归

优化

因为我们遍历了所有的可能

那，还有什么地方可以优化吗

我们继续

之前的数据可能不太好看，我们稍微调整一下，比如

N = 4
V = 5
v = [1,1,2,3]
w = [2,2,4,4]

我们添加了一个物品，新添加的物品和原来第一个一样

我们很容易看出：选择1和选择2，是一样的；选择1+2和选择3也是一样的

因为他们或他们的和 体积和价值完全一样

因选择他们中的一个而拆分出的子问题，有很大一部分是重叠的

但是在我们的计算中，子问题被计算了两次，重复了

为了避免重复计算

我们可以将子问题的解进行缓存，当第二次遇到同样的子问题时，直接返回已求出的解就可以了

回顾一下我们拆分子问题的过程

1. 选择一个物品
2. 剩余背包的体积和剩余物品组成了一个子问题

或

1. 选择另一个物品（前一个物品不选，既选前一个又选当前这种情况不在此考虑，因为会被前一个物品选择后拆分出的子问题覆盖）
2. 剩余背包的体积和其后物品组成了一个子问题（之所以是其后，原因同上）

其实第一种是第二种的特殊表现，可以归到第二种去

由此可见，子问题的唯一性由剩余背包的体积，和当前选择物品的后续物品组成，而后续物品的结尾位置是相同的，我们只需要知道起始位置就够了

体积的范围为0 - V，位置范围为0 - N

子问题的解是一个数值

所以我们可以在第一次遇到子问题时，将其解缓存到一个二维数组中，下次再遇到时，直接返回

以上，我们通过递归加记忆化的方式，优化了此问题

优化后，子问题的范围最多有V * N种

反向求解

那既然子问题的解是有限的

那我们可不可以先把所有子问题的解全求出来，然后在求出整个问题的解

当然可以，这种方式也就是所谓的递推

递推是递归的逆向

递归时，我们直接求解大问题，当大问题需要用到子问题的解时，再对子问题进行求解

递推时，我们通过已知小问题的解，推出更大问题的解，推导方向为最终的问题

那哪些问题的解是已知的？

我们之前递归时提到

直到物品没了或背包满了，无需继续拆分为止

无需拆分，也就是说当前问题的解已经的已知的了

显而易见，没物品可选和无空间可装，问题的解都是0

我们从这个最小的问题，一步步构造大问题

比这个小问题稍微大点的问题是什么？

物品多一个，或背包大一点

物品多一个，就多了一种可能，可能选了这个物品，总价值变的更高了，如果选择当前物品不能使总价值更高，那最高的总价值还是和之前的小问题一样，不会更差

若要选择多出来的这个物品，那意味着这个物品要占用一部分背包容量，即v[k]，如果整个背包容量还装不下这个物品，那这个物品也就无法选择，若能装下，那选择这个物品的总价值为w[k] + （去掉这个物品所占用的空间、去掉这个物品所组成的小问题的最高价值）

若不选多出来的这个物品，那最高价值和少一个物品且同样背包容量组成的小问题的解一样

选或不选，两种情况取较大的那个，也就是这个变大了的问题的解

背包大一点，同样是多了一种可能，原来不能选择的物品，现在也许可以选了

计算方式同上

总结

总结一下

设i为物品范围，从0-N；j为背包容量，从0-V

f(i, j)表示为前i个物品，在背包容量为j的情况下的解

若i = 0 或 j = 0
则f(i, j) = 0

否则
f(i, j) = max(
    w[i] + f(i - 1, j - v[i]), // 选择当前物品，若物品占用空间超过背包容量则为0
    f(i - 1, j) // 不选当前物品
)

至于Wiki，动态规划是分解问题并求解的方法，但分解问题并求解的并不一定是动态规划