算法练习4：爬楼梯和挖金矿（动态规划）

2021-04-06  本文已影响0人  miao8862

所谓动态规划，其实就是使用分治的方法将问题最简化，再从简化的步骤再逆推回复杂问题的最优解。和归并排序的思想很类似。

爬楼梯

题目：如果有n阶楼梯，你一次只能爬一阶或二阶两种爬法，问到达n阶一共有几种爬法？

爬楼梯-自顶向下-递归解法

按照动态规划的方法，先是自顶向下，从最后解开始得答案：

  1. 到达n阶的方法，自然是n-1走1阶或者n-2走2阶这两种；所以n就是(到达n-1的方法)和(到达n-2的方法)之和，用公式就是f(n) = f(n-1) + f(n-2)
  2. 到达n-1的方法，自然又是n-2走1阶或者n-3走2阶这两种；f(n-1) = f(n-2) + f(n-3)
  3. 到达n-2的方法，就是n-3走1除非或者n-4走2除非这两种：f(n=2) = f(f-3) + f(n-4)
    ....
  4. 直到到达2楼梯时，只有2种：就是1阶1阶走，或者走2阶，这就是我们说的边界值， f(2) = 2
  5. 到达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)

可以看出才到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 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个去挖，怎么分配能挖到的金矿最多呢？

采金矿-自顶向下-递归解法

解题思想：

下面，为了简化问题，我就拿a分支来举例：

所以对于a分支各个分支来说，它的解分别为：900kg, 600kg, 700kg, 750kg, 400kg，最优解是900kg

b分支也同理
它的解分别是：0，350kg，650kg，550kg，500kg，850kg，800kg，700kg，最优解是850kg

最后，a、b分支比较，最优解为900kg
可以看得出来，每个分支的最优解，就是它再下面分支的最大解，所以只要判断出什么情况下会出现这个分支就是解决问题的关键，而这个关系，用数学公式来表达的话，就叫状态转移方程式。

回到这句话：只要剩余人数够挖这个金矿，那么它就有两种情况，挖这个金矿和不挖这个金矿；如果人数不够挖这个金矿，那就只有一种情况，忽略这个金矿，因为挖不了

以上总结起来：
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)

上一篇下一篇

猜你喜欢

热点阅读