动态规划（Dynamic Programming）
基本概念
Those who cannot remember the past are condemned to repeat it
那些不能记住过去的人注定要不停的重复
The idea is to simply store the results of subproblems， so that we do not have to re-compute them when needed later
动态规划本质是存储子问题的结果，使得在后续计算过程中可以直接使用这些结果，减少了重复计算的部分。
我们需要将一个问题分解成一系列重叠的子问题，然后根据这些子问题的答案逐渐构造更大的子问题的答案，最终完成原始的问题。如果有个问题，它可以被分解成一系列小的子问题，这些子问题又能被分解成更小的子问题，如果一些子问题又是有重叠的，那么原始问题就是一个动态的规划问题（DP problem）
DP的核心思想是通过记录求解过程中的部分结果已避免重复计算。这个概念也应用在了实际生活的各个场景。
DP 可以让原本计算复杂度在指数级别的问题缩减到平方级或立方级别
一份来自于Quora的答案
3732FD8E-0F48-4407-AE1C-4EDC4DCC45FB.png
下面用斐波那契函数的递归和DP实现阐述DP的思想
我们使用的递归使用递归函数的其它值表达改递归函数的当前值。
0C7AC485-B466-49E6-956F-52C4D4F078EF.png
斐波那契函数的递归实现
int fib (int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2);
}
以上递归实现斐波那契，简单直观，可读性强，但是会引入许多重复计算，如下图所示：
0BD322AE-EA2B-429E-9691-650C1C2A1943.png
而一般的思路是我们提前计算好递归函数需要的值并存储（空间换时间），用于后续的子问题计算，这要比递归快很多（因为省去了重复计算的步骤）,
void fib () {
fibresult[0] = 1;
fibresult[1] = 1;
for (int I = 2; I<n; I++)
fibresult[i] = fibresult[i-1] + fibresult[i-2];
}
以上就是用动态规划实现斐波那契
大多数动态规划问题可以分为两种类型
- 求解问题的最优解（Optimization Problems）
- 求解问题的组合（Combinatorial Problems）
最优解期望选择一个最佳方案，使得最终结果（某个值）最大或者最小；组合问题则是期望能计算出某个事件的可能性或者做一件事情的方法数
使用DP解决问题
DP问题的通用步骤模式：
- 问题可以被分解成子问题
- 问题的解可以递归的用子问题的解进行表示
- 自底向上（bottom-up）计算子问题的解
- 通过已经计算的子问题解构造父问题的最优解，最终获得原始问题的解。
一个例子：
你收藏了N瓶葡萄酒，这些葡萄酒用1—N进行标识，从左到右放在架子上。第i瓶葡萄酒的价格是pi。
葡萄酒储存的时间越长，价格越高。加入今天是第一年，那么第y年的第i瓶的葡萄酒价格是 y*pi
你从今年开始，每一年卖一瓶葡萄酒，卖酒的规则如下：
只能选架子上最左或最右边的酒
不能对架子上酒进行重新排序
你想得出，如果你以最优的顺序卖酒，能获得的最大利润是多少？
举例说明：
如果葡萄酒的价格是（按照它们在架子上从左到右的顺序）：
p1=2, p2=3, p3=5, p4=1, p5=4。
直观的想法是尽早卖出的便宜的酒，贵的酒越晚卖，最后的收益越高，因此可能的答案是：
按照 p1, p2, p5, p4, p3 的顺序卖酒，因此总收入是：
2 * 1 + 3 * 2 + 4 * 3 + 1 * 4 + 5 * 5 = 49
答案是错的
如果按照以下的顺序（p1, p5, p4, p2, p3 ），总收入是：
2 * 1 + 4 * 2 + 1 * 3 + 3 * 4 + 5 * 5 = 50
看来问题不是这么简单，下面通过backtrack（回朔）法解决此问题，进而在backtrack的基础上使用DP进行优化
当需要通过记录法（就是实现DP的一种方式）解决一个问题的时候，可以从使用回朔（backtrack）法发现正确答案开始。回朔法枚举所有答案然后选择最佳答案。
以下是有关回朔法的一些准则
- 实现回朔的是递归函数
- 函数中应该通过return语句返回答案，而不是将答案存储在某个地方
- 所有函数用到的非本地变量都应该是只读的。函数只能修改它的本地变量和它的参数
int p[N]; // 函数外的全局变量是只读的
/**
year 代表当前年（从1开始）
[be, en]代表架子上未售的葡萄酒的启示和结束标识
**/
int profit(int year, int be, int en) {
//架子上的酒已经卖空
if (be > en)
return 0;
// 尝试从出售架子上最左边或最右边的酒，递归计算答案，然后选择利润最高的
return max(
profit(year + 1, be + 1, en) + year * p[be],
profit(year + 1, be, en - 1) + year * p[en]);
)
}
以上实现方式简单的尝试卖酒的所有的可能顺序。如果开始有N瓶酒要卖，会有2的N次方的可能（每年都有两种选择）。所以以上算法的时间复杂度的是指数级别的。
下面在回朔法的基础上采用记录的方式记录子问题的结果，避免重复计算，从而提升效率（即是采用DP进行优化）
在使用DP前，首先尽量简化递归函数中不必要的参数，要么这个参数可以通过其它参数构造，要么这个参数可以被删除，上例中year（当前年）这个参数是多余的，因为year可以通过葡萄酒的总数以及当前未售的的葡萄酒树计算出来：
year = N - 未售的葡萄酒数目 + 1， 而未售的葡萄酒数目 = en - be +1
所以递归函数可以简化参数为：
int N; // 只读的葡萄酒起始总数
int p[N]; // 只读的葡萄酒价格数组
int profit(int be, int en) {
if (be > en)
return 0;
// (en - be + 1)是未售的葡萄酒总数
int year = N - ( en - be + 1) + 1;
return max(
profit(be + 1, en) + year * p[be],
profit(be, en - 1) + year * p[en]
);
}
继续把复杂度是2的N次方的回朔函数转换为使用记录法使得复杂度是N平方的函数，最直接的方法是 缓存已经计算好的结果，如下所示
int N;
int p[N];
int cach[N][N]; //缓存计算的售出的葡萄酒的价值
int profit(int be, int en) {
if (be > en)
return 0;
// 如果已经算过了，则返回缓存的值
if (cache[be][en] != -1)
return cache[be][en];
int year = N - (en - be + 1);
// 缓存计算的中间值
return cache[be][en] = max(
profit(be + 1, en) + year * p[be],
profit(be, en - 1) + year * p[en]
);
}
总结：
如果你识别出一个问题可以用DP解决，首先尝试用一个回朔函数计算正确答案，然后删除回朔函数中的冗余参数以及优化单个函数的计算时间复杂度（可以把递归调用看作是O(1)复杂度的调用），最后，记录函数返回值避免同样的数据计算两次。
实际应用以上准则，解决经典背包问题
问题描述：
假设你是小偷，背着一个可装4磅东西的背包，你可盗窃的商品有如下4件
音响（4磅， 3000美元）
笔记本电脑（3磅， 2000美元）
吉他（1磅， 1500美元）
IPHONE（1磅， 2000美元 ）
为了让盗窃的商品价值最高，你该选择那些商品
分析：这是一个DP问题，因为可以把一个大问题分解成若干子问题
把IPHONE从原始物品中先拿出
子问题1: [音响、笔记本电脑、吉他] 放入4磅包中的最优解。
子问题2: [音响、笔记本电脑、吉他] 放入另一个小包中的最优解，这个小包的容量是（原包的容量 - IPHONE的容量）
那么原问题的解 ：
if （子问题2的解的价值 + IPHONE的价值 > 子问题1的解的价值） &&
( 子问题2的解的容量 + IPHONE的容量 <= 原包的容量) then
问题的解 = {
价值： 子问题2的价值+IPHONE的价值，
容量： 子问题2的容量 + IPHONE的容量
} else
问题的解 = 子问题1的解
子问题1和子问题2 又可以分解为其它的子问题
以下是使用JavaScript的源码：
// 经典背包问题
const ITEMS = [
{ name: “iphone”, w: 1, p: 2000 },
{ name: “laptop”, w: 3, p: 2000 },
{ name: “gita”, w: 1, p: 1500 },
{ name: “speaker”, w: 4, p: 3000 }
];
const WEIGHT_OF_BAG = 4;
// 通过回朔法解决背包问题
function solveBagByBackTrack(wOfB, items) {
if (wOfB <= 0 || items.length === 0) {
return { w: 0, p: 0, resultOfItems: [] };
}
const element = items[items.length - 1];
// 获取除了最后一个item之外的最优解（背包总重量不变）
const lastResult = solveBagByBackTrack(
wOfB,
items.slice(0, items.length - 1)
);
// 获取除了最后一个item之外的最优解（背包重量 = 背包总重量 - 待加入的物品重量）
const resultNoItem = solveBagByBackTrack(
wOfB - element.w,
items.slice(0, items.length - 1)
);
const updatedP = element.p + resultNoItem.p;
const updatedW = element.w + resultNoItem.w;
// 关键：如果背包中加了当前物品后的价值大于之前的价值，并且加入物品后没有超重，说明当前物品可以加入到背包中，否则不加入到背包中
if (updatedP > lastResult.p && updatedW <= wOfB) {
w = updatedW;
p = updatedP;
resultOfItems = […resultNoItem.resultOfItems, element];
return { w, p, resultOfItems };
} else {
return lastResult;
}
}
//test
(() => {
const resultBk = solveBagByBackTrack(WEIGHT_OF_BAG, ITEMS);
console.log(`back track result is ${JSON.stringify(resultBk)}`);
输出结果是
back track result is {"w":4,"p":4000,"resultOfItems":[{"name":"iphone","w":1,"p":2000},{"name":"laptop","w":3,"p":2000}]}
偷 笔记本电脑和IPHONE可以达到最大价值
回朔法搞定后，优化为DP，最简单的方式就是使用额外的空间，记录子问题的结果，以下使用JavaScript实现的DP解法，采用一个MAP进行结果的缓存，😄
//通过动态规划解决背包问题，主要是通过记录之前子问题的解，不需要重复计算了
const CACHE = new Map();
function sovleBagByDp(wOfB, items) {
if (wOfB <= 0 || items.length === 0) {
return { w: 0, p: 0, resultOfItems: [] };
}
const element = items[items.length - 1];
let lastResult;
if (CACHE.has(`${wOfB}-${items.length - 1}`)) {
console.log(`hit it ${wOfB}-${items.length - 1}`);
lastResult = CACHE.get(`${wOfB}-${items.length - 1}`);
} else {
lastResult = sovleBagByDp(wOfB, items.slice(0, items.length - 1));
//console.log(`set it ${wOfB}-${items.length - 1}`);
CACHE.set(`${wOfB}-${items.length - 1}`, lastResult);
}
let resultNoItem;
if (CACHE.has(`${wOfB - element.w}-${items.length - 1}`)) {
console.log(`hit it ${wOfB - element.w}-${items.length - 1}`);
resultNoItem = CACHE.get(`${wOfB - element.w}-${items.length - 1}`);
} else {
resultNoItem = sovleBagByDp(
wOfB - element.w,
items.slice(0, items.length - 1)
);
//console.log(`set it ${wOfB - element.w}-${items.length - 1}`);
CACHE.set(`${wOfB - element.w}-${items.length - 1}`, resultNoItem);
}
const updatedP = element.p + resultNoItem.p;
const updatedW = element.w + resultNoItem.w;
if (updatedP > lastResult.p && updatedW <= wOfB) {
w = updatedW;
p = updatedP;
resultOfItems = […resultNoItem.resultOfItems, element];
return { w, p, resultOfItems };
} else {
return lastResult;
}
}
//test
(() => {
CACHE.clear();
const resultDp = sovleBagByDp(WEIGHT_OF_BAG, ITEMS);
console.log(`dp result is ${JSON.stringify(resultDp)}`);
})();
输出结果是
back track result is {"w":4,"p":4000,"resultOfItems":[{"name":"iphone","w":1,"p":2000},{"name":"laptop","w":3,"p":2000}]}
和使用回朔法一致
这套算法可以用在类似的问题场景，比如旅游行程最大化问题。假设你要到南京度假，想去的地方很多，但是因为假期只有两天，没法去每个地方浏览
因此列了单子
w 表示 需要浏览的天数， p表示评分
{ name: "瞻园”, w: 0.5, p: 7 },
{ name: “白鹭洲公园”, w: 0.5, p: 6 },
{ name: “明孝陵”, w: 1, p: 9 },
{ name: “南京博物院”, w: 2, p: 9 },
{ name: “老门东”, w: 0.5, p: 8 }
因此上面的背包问题测试可以直接换成这套数据
//旅游行程最大化
const ITEMS_NANJING = [
{ name: “瞻园”, w: 0.5, p: 7 },
{ name: “白鹭洲公园”, w: 0.5, p: 6 },
{ name: “明孝陵”, w: 1, p: 9 },
{ name: “南京博物院”, w: 2, p: 9 },
{ name: “老门东”, w: 0.5, p: 8 }
];
const DAYS = 2;
//test
(() => {
const tourOfResultBk = solveBagByBackTrack(DAYS, ITEMS_NANJING);
console.log(`back track tourOfResult is ${JSON.stringify(tourOfResultBk)}`);
CACHE.clear();
const tourOfResultDp = sovleBagByDp(DAYS, ITEMS_NANJING);
console.log(`dp tourOfResult is ${JSON.stringify(tourOfResultDp)}`);
})();
结果无论是回朔法还是DP都是一样的
back track tourOfResult is {"w":2,"p":24,"resultOfItems":[{"name":"瞻园","w":0.5,"p":7},{"name":"明孝陵","w":1,"p":9},{"name":"老门东","w":0.5,"p":8}]}
dp tourOfResult is {"w":2,"p":24,"resultOfItems":[{"name":"瞻园","w":0.5,"p":7},{"name":"明孝陵","w":1,"p":9},{"name":"老门东","w":0.5,"p":8}]}
网友评论