两个动态规划问题-一一网

这是我参与更文挑战的第2天，活动详情查看：更文挑战

基本概念

动态规划英文 Dynamic Programming，是求解决策过程最优化的数学方法，后来沿用到了编程领域。
动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程，从简单的初始状态一步一步递推，最终得到复杂问题的最优解。
动态规划解决问题的过程分为两步：

寻找状态转移方程
利用状态转移方程式自底向上求解问题

爬楼梯问题

假设有n阶楼梯，爬楼梯的方式只有一次爬1阶或者一次爬2阶，问爬完n阶楼梯共有几种方式。

最后一次的爬楼梯的方式:
- 爬到n-1，爬1阶
- 爬到n-2，爬2阶

推导方程式：

$f(n)=f(n-1) + f(n-2)$

// 时间复杂度O(N)，空间复杂度O(1)
function climbingWays(n) { // 爬到n阶楼梯的方法个数

  // 假设楼梯一次只能爬一级或者两级
  
  if(n < 1) {
    return 0;
  }

  if(n === 1) {
    return 1;
  }

  if(n === 2) {
    return 2;
  }

  // 由于爬楼梯阶层只需要前两级阶层的个数，只需保存两个数就可以
  var a = 1;
  var b = 2;
  var temp = 0;

  for(var i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }

  return temp;

}
复制代码

挖金矿问题

假设有n个金矿，w个工人，每座金矿需要的工人和金矿量分别用p[]和g[]来表示。
问：所有工人挖去金矿的最大值。

由于最后一座金矿有两种情况：挖或者不挖。

最大子结构有两种情况：
- w个工人挖n-1个金矿
- w-p[n-1]个工人挖n-1个金矿 + g[n-1]
边界情况
- 人手不够，不够挖一座金矿，或者没有金矿
- 所有人挖第一座金矿

状态转移方程

f(n, w) = 0 (n <= 1, w < p[0]) 无金矿或者人手不足
f(n, w) = g[0] (n == 1, w >= p[0]) 人手足够，只挖第一个金矿
f(n, w) = f(n-1, w) (n > 1, w < p[n-1]) 剩余人数少于这个金矿的所需人数
f(n, w) = max(f(n-1, w), f(n-1, w – p[n-1]) + g[n-1]) (n > 1, w >= p[n-1]) 工人充足的情况


function getMostGold(num, workers, gold, person) {

  var preResult = [];
  var result = [];

  // 先判断边界条件
  for(var i = 0; i <= num; i++) {
      if(i < person[0]) {
        preResult[i] = 0;
      } else {
        preResult[i] = gold[0];
      }
  }

  // 从第二行开始，按照前一行的数据进行计算
  // i代表第i座金矿，j代表当前工人个数
  for(var i = 0; i < num; i++) {

    for(var j = 0; j <= workers; j++) {
      if(j < person[i]) {
        result[j] = preResult[j];
      } else {
        result[j] = Math.max(preResult[j], preResult[j-person[i]]+gold[i])
      }
    }

    // 把当前的值传给上一层，继续遍历
    preResult = result;
  }

  return result[num]; // 最后返回最大值
}

复制代码