所谓动态规划，其实就是使用分治的方法将问题最简化，再从简化的步骤再逆推回复杂问题的最优解。和归并排序的思想很类似。
爬楼梯
题目：如果有n阶楼梯，你一次只能爬一阶或二阶两种爬法，问到达n阶一共有几种爬法？
爬楼梯-自顶向下-递归解法
按照动态规划的方法，先是自顶向下，从最后解开始得答案：
- 到达n阶的方法，自然是n-1走1阶或者n-2走2阶这两种；所以n就是(到达n-1的方法)和(到达n-2的方法)之和，用公式就是f(n) = f(n-1) + f(n-2)
- 到达n-1的方法，自然又是n-2走1阶或者n-3走2阶这两种；f(n-1) = f(n-2) + f(n-3)
- 到达n-2的方法，就是n-3走1除非或者n-4走2除非这两种：f(n=2) = f(f-3) + f(n-4)
.... - 直到到达2楼梯时，只有2种：就是1阶1阶走，或者走2阶，这就是我们说的边界值， f(2) = 2
- 到达1阶楼梯的方法，只有1种，就是开始走1阶， f(1) = 1
所以按照以上公式可以得出：
f(n) = n, （n<=2）
f(n-1) + f(n-2), (n>2)
按照这个思路，其实可以看出它每次都分割成2个分支，然后分割次数为n-1次，所以它的时间复杂度为O(2^n-1) ，约等于O(2^n)，是指数级别的
它的实现也很简单:
function climbStairs(n) {
if(n <= 2) {
return n;
}
return climbStairs(n-1) + climbStairs(n-2)
}
console.time()
console.log(climbStairs(45)); // 1836311903
console.timeEnd() // default: 7589.035ms
爬楼梯-自顶向下-备忘录解法
使用自顶向下的方法，虽然能解出问题，但指数级的时间复杂度过高，呃..当我运行要到100阶时，55s了还没运行完，受不了，直接强制关掉！
我们可以查看它的实现，会发现它其实有很多重复运算，比如：
f(5) = f(4) + f(3)
-
对于到达4阶的分支:
f(4) = f(3) + f(2)- 3分支：
f(3) = f(2) + f(1)
f(2) = 2
f(1) = 1 - 2分支：
f(2) = 2
f(1) = 1
- 3分支：
-
对于到达3阶的分支
f(3) = f(2) + f(1)
f(2) = 2
f(1) = 1- 2分支：
f(2) = 2
f(1) = 1 - 1分支：
f(1) = 1
- 2分支：
可以看出才到5阶这个过程就已经重复了计算f(1), f(2), f(3)好几次，如果到n阶，这些计算不是还要重复很多次，这根本就是不必要的。我们每一次的运算其实都可以利用上一次的结果，所以只需要运用缓存来存储上一次的结果，再一次调用时，直接获取结果就好，这就是我们说的备忘录算法。
按照这个思想，我们优化得到：
function climbStairs2(n,map) {
let value = 0;
if(n <= 2) {
return n;
}
if(map.get(n)) {
return map.get(n)
}else {
value = climbStairs2(n-1, map) + climbStairs2(n-2, map)
map.set(n, value)
return value
}
}
console.time()
// 创建一个哈希表，用来存储已经计算过的n阶结果
console.log(climbStairs2(45, new Map())); // 1836311903
console.timeEnd() // default: 2.263ms
这时候可以看到所用时长，已经减少了很多，看看现在的复杂度：
- 时间复杂度：只用1次计算F(n)-F(1)的结果，所以是O(n)
- 空间复杂度：要存储从F(n)-F(1)的结果，所以是O(n)
爬楼梯-自底向上-动态规划解法(优化空间复杂度)
既然我们要算上层的结果，必须要先递归得到下层的结果，然后再整合得回上层结果（上-下-上），为什么不干脆反过来，我先拿到下层结果，再直接递推到上层，不就省了第一步从上到下的递归步骤？
| 楼梯数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 走法数 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | ... |
看结果，是不是很像斐波那契数列，只不过它从1和2开始而已。这时，我们的实现：
function climbStairs3(n) {
// 因为2是边界值，1阶是1种方法，2阶是2种方法，所以循环从3阶开始
let s1 = 1; // 记录到达n-2阶的方法数
let s2 = 2; // 记录到达n-1阶的方法数
let s = 0; // 记录到达n阶的方法
for(let i = 3; i <= n; i++) {
s = s1 + s2
s1 = s2
s2 = s
}
return s;
}
console.time()
console.log(climbStairs3(45)); // 1836311903
console.timeEnd() // default: 2.223ms
这时候时间复杂度还是O(n)，空间复杂时因为只用了3个变量值，是常量级，所以已经变成了O(1)
下面再以一个采金矿的问题进一步说明
采金矿
题目：
有5个金矿：
第1个金矿400kg，需要5个人挖，
第2个金矿500kg，需要5个人挖
第3个金矿200kg，需要3个人挖
第4个金矿300kg，需要4个人挖
第5个金矿350kg，需要3个人挖
问，总共只能有10个去挖，怎么分配能挖到的金矿最多呢？
采金矿-自顶向下-递归解法
解题思想：
-
只要剩余人数够挖这个金矿，那么它就有两种情况，挖这个金矿和不挖这个金矿；如果人数不够挖这个金矿，那就只有一种情况，忽略这个金矿，因为挖不了
-
初始有10个人，对于第1个金矿（400kg）来说：
a.挖：要5人 ，得400kg金矿，剩5个人：
b. 不挖，不用人，没有金矿，剩10人；
下面，为了简化问题，我就拿a分支来举例：
-
对第二个金矿（500kg）来说，要5个人：
a.1 剩5人，挖，则用5人，剩0人，得金400+500kg=900kg，这个分支结束
a.2 剩5人，不挖，用0人，得金还是之前的400kg，剩5人 -
对于第三个金矿（200kg）来说，要3个人：
a.2.1，之前剩5人，挖，用3人，得金200+400kg=600kg，最后剩2人
a.2.2，之前剩5人，不挖，用0人，得金不变400kg，最后剩5人 -
对于第四个金矿（300kg）来说，要4个人：
a.2.1，之前剩2人，不能挖，忽略这个金矿，保持600kg
a.2.2.1 之前剩5个，挖，用4人，得金300kg+400kg，最后剩1人
a.2.2.2 之前剩5个，不挖，用0人，得金和前面一样400kg，最后剩5人 -
对于第五个金(350g)来说，要3个人:
a.2.1，之前剩2人，还是不能挖，忽略这个金矿，此时没有金矿了，分支结束，所以这个分支保持600kg
a.2.2.1 之前剩1个，不能挖，忽略这个金矿，此时没有金矿了，分支结束，所以这个分支保持700kg
a.2.2.2.1 之前剩5个，挖，用3人，分支结束，得金350kg+400kg=750kg，最后剩2人
a.2.2.2.2 之前剩5个，不挖，用0人，保持得金400kg，最后剩5人
所以对于a分支各个分支来说，它的解分别为：900kg, 600kg, 700kg, 750kg, 400kg，最优解是900kg
b分支也同理
它的解分别是：0，350kg，650kg，550kg，500kg，850kg，800kg，700kg，最优解是850kg
最后，a、b分支比较，最优解为900kg
可以看得出来，每个分支的最优解，就是它再下面分支的最大解，所以只要判断出什么情况下会出现这个分支就是解决问题的关键，而这个关系，用数学公式来表达的话，就叫状态转移方程式。
回到这句话：只要剩余人数够挖这个金矿，那么它就有两种情况，挖这个金矿和不挖这个金矿；如果人数不够挖这个金矿，那就只有一种情况，忽略这个金矿，因为挖不了
- 假设金矿分布为g: [400, 500, 200, 300, 350]
- 金矿数所需人数对应为p: [5, 5, 3, 4, 3 ]
- 剩余人数表示为w
当w（当剩余人数） < p[n-1]（当前金矿数所要人数）时，人力不足， 没资格挖，会直接忽略当前金矿，跳到下一个金矿，所以此时f(n,w) = f(n-1, w)
当w>p(n-1)时，就会分为两个分支:- 一个是挖当前金矿f(n-1, w - p[n-1]) + g[n-1]，g[n-1]是当前金矿数，p[n-1]是挖当前金矿所而人数，w-p[n-1]是下一次剩余人数，n-1是下一个金矿
- 一种是不挖当前金矿f(n-1, w)，则剩余人数不变，直接到下一个金矿（视金钱为粪土，我有人也不挖！）
然后地主爸爸都是贪心的，虽然我分两条路走，但是哪个有钱我要哪个！所以他要分支中金最多的那个仔！
以上总结起来：
0, (n=0 || w=0，即没矿或没人时)
F(n,w) = F(n-1, w), (n>=1且w<p[n-1], 人数不足以挖当前金矿时，忽略当前的金矿，直接找下一个金矿)
max(F(n-1, w), F(n-1, w-p[n-1]) + g[n-1]), (n>=1且w>=p[n-1]) ,人数充足时，为两分支中的最大值
/**
* @param w: 工人数
* @param n: 可挖金矿数
* @param p: 金矿开采所需的工人数量
* @param g: 金矿含量
*/
function getBestGold(w, n, p, g) {
// 如果剩余工人数或剩余采矿数为0，则可供可继续采矿量为0
if(w===0 || n===0) {
return 0;
}
// 如果剩余人数小于金矿所需人数，则忽略此金矿，去采下一个金矿
if(w < p[n-1]) {
getBestGold(w, n-1, p, g)
}
// 如果剩余人数充足，则返回采集下一个金矿和不采集下一个金矿中的最大值
return Math.max(getBestGold(w, n-1, p, g), getBestGold(w-p[n-1], n-1, p, g) + g[n-1])
}
let w = 10 // 剩余挖矿人数
let p = [5, 5, 3, 4, 3] // 每个矿需要的挖矿人数
let g = [400, 500, 200, 300, 350] // 每个矿的金矿含量
console.time()
console.log(getBestGold(w, g.length, p, g)); // // 900
console.timeEnd() // default: 2.675ms
可以看到，这个方法的时间复杂度是O(2^n)，属于能做，就是慢....
采金矿-自顶向下-备忘录解法
从刚刚爬楼梯的例子类似，自顶向下之所以慢，是因为它做了很多重复的操作，这时我们同样使用一个哈希表来存储每种金矿分配情况的值，减少重复操作
注意，这时的key，是有两个自变量的，一个金矿对应的个数，一个是当前剩余工人数
function getBestGold2(w, n, p, g, map) {
// console.log('map:', map);
// 如果剩余工人数或剩余采矿数为0，则可供可继续采矿量为0
if((w===0) || (n===0)) {
return 0;
}
// 如果剩余人数小于金矿所需人数，则忽略此金矿，去采下一个金矿
if(w < p[n-1]) {
return getBestGold2(w, n-1, p, g, map)
}
// 如果剩余人数充足，则返回采集下一个金矿和不采集下一个金矿中的最大值
// 获取哈希表中的key，当前的key是由两个变量控制的，金矿对应个数和当前剩余工人数
let key = JSON.stringify([w, n])
// 判断哈希表中，是否有当前key的值，如果有，直接取值
if(map.get(key)) {
return map.get(key)
}else {
// 如果没有，则计算
let value = Math.max(getBestGold2(w, n-1, p, g, map), getBestGold2(w-p[n-1], n-1, p, g, map) + g[n-1])
map.set(key, value)
return value
}
}
console.time()
console.log(getBestGold2(w, g.length, p, g, new Map())); // // 900
console.timeEnd() // default: 2.675ms
可以看出，这时候的时间复杂度近似是O(nw)，空间复杂度也同样的是O(nw)
采金矿-自底向上-动态规划解法
在爬楼梯的例子里，因为变量只有一个n，所以比较简单。但在金矿的例子里，有两个变量，所以这时，我们借助一个二维表来分析：
| 剩余工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 金矿2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 金矿3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 金矿4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 金矿5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
对于第一个金矿来说，人数(5人)不足时，不能采，人数足时，只有一个金矿，只能采当前金矿（400kg）：
当然也可以套公式:
F(1,5) = max(F(0,5), F(0,0) + G[0]) = max(0, 0+ 400) = 400
| 剩余工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 400 | 400 | 400 | 400 | 400 | 400 |
对于第二个金矿来说，人数(5人)不足时，也不能采，当够5人时，可以采当前金矿(G[1]，500kg)，就可以套公式了:
F(2, 5) = max(F(1, 5), F(1,0) + G[1])， F(1, 5)查表，400kg；F(1,0)边界值为0，G[1]为当前金矿500kg，最大值为500kg
F(2, 6) = max(F(1, 5), F(1,1) + G[1])， F(1, 5)查表，400kg；F(1,1)查表为0，G[1]为当前金矿500kg，最大值为500kg
...
F(2, 10) = max(F(1, 5), F(1,5) + G[1])， F(1, 5)查表，400kg；G[1]为当前金矿500kg，最大值为400+500=900kg
| 剩余工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 400 | 400 | 400 | 400 | 400 | 400 |
| 金矿2 | 0 | 0 | 0 | 0 | 500 | 500 | 500 | 500 | 500 | 900 |
对于第三个金矿来说，人数(3人)不足时，也不能采，当够3人时，可以采当前金矿(G[2] 200kg)，就可以套公式了:
F(3,3) = max(F(2,4), F(2,0) + G[2]) = max(0, 0 + 200) = 200
F(3,4) = max(F(2,4), F(2,1) + G[2]) = max(0, 0 + 200) = 200
F(3,5) = max(F(2,5), F(2,2) + G[2]) = max(500, 0 + 200) = 500
...
F(3,10) = max(F(2,10), F(2,7) + G[2]) = max(900, 500 + 200) = 900
| 剩余工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 400 | 400 | 400 | 400 | 400 | 400 |
| 金矿2 | 0 | 0 | 0 | 0 | 500 | 500 | 500 | 500 | 500 | 900 |
| 金矿3 | 0 | 0 | 200 | 200 | 500 | 500 | 500 | 700 | 700 | 900 |
对于第四个金矿来说，人数(4人)不足时，也不能采当前矿，递推采以前的；当够4人时，可以采当前金矿(G[3] 300kg)，就可以套公式了:
F(4,3) = F(3,3) = 200，人数不足时，等于上一个金矿对应人数的值
F(4,4) = max(F(3,4), F(3,0) + G[3]) = max(200, 0 + 300) = 300
F(4,5) = max(F(3,5), F(3,1) + G[3]) = max(500, 0 + 300) = 500
...
F(4,10) = max(F(3,10), F(3,6) + G[3]) = max(900, 500 + 300) = 900
| 剩余工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 400 | 400 | 400 | 400 | 400 | 400 |
| 金矿2 | 0 | 0 | 0 | 0 | 500 | 500 | 500 | 500 | 500 | 900 |
| 金矿3 | 0 | 0 | 200 | 200 | 500 | 500 | 500 | 700 | 700 | 900 |
| 金矿4 | 0 | 0 | 200 | 300 | 500 | 500 | 500 | 700 | 800 | 900 |
对于第五个金矿来说，人数(3人)不足时，也不能采（只能采以前的，发现以前的也都不能采）；当够3人时，可以采当前金矿(G[4] 350kg)，就可以套公式了:
F(5,3) = max(F(4,3), F(4,0) + G[4]) = max(200, 0 + 350) = 350
F(5,4) = max(F(4,4), F(4,1) + G[4) = max(300, 0 + 350) = 350
F(5,5) = max(F(4,5), F(4,2) + G[4]) = max(500, 0 + 350) = 500
...
F(5,10) = max(F(4,10), F(4,7) + G[4]) = max(900, 500 + 350) = 900
| 工人数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 金矿1 | 0 | 0 | 0 | 0 | 400 | 400 | 400 | 400 | 400 | 400 |
| 金矿2 | 0 | 0 | 0 | 0 | 500 | 500 | 500 | 500 | 500 | 900 |
| 金矿3 | 0 | 0 | 200 | 200 | 500 | 500 | 500 | 700 | 700 | 900 |
| 金矿4 | 0 | 0 | 200 | 300 | 500 | 500 | 500 | 700 | 800 | 900 |
| 金矿5 | 0 | 0 | 350 | 350 | 500 | 550 | 650 | 850 | 850 | 900 |
推导完后，大家开始来找规律了
用代码实现方式为：
function getBestGold3(w,n, p, g) {
plen = p.length
let preArr = new Array(w)
let curArr = new Array(w)
// 添加第一行边界值
for(let i = 0; i <= w; i++) {
// 当人数少于第一个金矿所需人数时，没金可挖
if(i < p[0]) {
preArr[i] = 0
// 当人数大于等于第一个金矿人数时，可以挖第一个金矿
}else {
preArr[i] = g[0]
}
}
// 遍历的金矿数（也就是行）
for(let i = 1; i < n; i++) {
// 遍历工人数（也就是每一个金矿的人数）
for(let j = 0; j <= w; j++) {
// 人数不足以挖当前金矿时，就等于上一行同列那个格式数
if(j < p[i]) {
curArr[j] = preArr[j]
// 如果人数充足时，就为 上一行同列格子数 和 上一行往前p[i]列的格式数+当前金矿数 这两数中的最大值
}else {
curArr[j] = Math.max(preArr[j], preArr[j - p[i]] + g[i])
}
}
preArr = [...curArr]
}
return curArr[w]
}
let w = 10 // 剩余挖矿人数
let p = [5, 5, 3, 4, 3] // 每个矿需要的挖矿人数
let g = [400, 500, 200, 300, 350] // 每个矿的金矿含量
console.time()
console.log(getBestGold3(w, p.length, p, g)); // 900
console.timeEnd() // default: 2.456ms
它的时间复杂度为O(n*w)， 空间复杂度为O(2w),约为O(w)
网友评论