前言

最近和朋友聊天,说起DP问题,想到大学时候学长上来一通“状态转移函数”把我们讲懵了,于是尝试写个入门笔记。

DP思想

通俗来说,动态规划解决问题的方法,就是当系统处于任何一个状态C,你去穷举所有状态A,然后把可能从A到达C的情况全部找出来,并从中获得最优解即可。所以,所谓的“状态转移方程”就是存在一条边从状态A到状态C,这条边的代价。简而言之,动态规划主要思想就是自底向上、局部最优到全局最优,通过计算每个子结构的最优解,求出总体结构的最优解。其目的是解决通过自顶向下的算法(如递归),带来的子结构重复计算,导致时间复杂度指数级上升的问题。

入门示例

桌上有 1kg、8kg、11kg 的三种砝码不限量供应,如何用最少数量砝码凑出 17kg 的量?

分析

设最少需要 n 个砝码,可以凑出 17kg 的量,设方程 f(x) 表示求 x(kg) 的量最少需要多少个砝码,那么我们有 :f(17kg) = n

现在,我们从 17kg 砝码中拿走一个,由于整体是最优的,所以子结构一定是最优的,即剩下的重量和砝码数量也一定满足我们的 f(x)。于是,我们一定有: min{f(17kg - 1kg), f(17kg - 8kg), f(17kg - 11kg)} = n - 1

所以,我们从已知结果 f(1kg) = 1f(8kg) = 1f(11kg) = 1 开始向上计算,直到 x 抵达 17kg即可。

计算过程

f(0) = 0
f(1kg) = 1
f(2kg) = f(1kg) + f(1kg) = 2
f(3kg) = f(2kg) + f(1kg) = 3
f(4kg) = f(3kg) + f(1kg) = 4
f(5kg) = f(4kg) + f(1kg) = 5
f(6kg) = f(5kg) + f(1kg) = 6
f(7kg) = f(6kg) + f(1kg) = 7
f(8kg) = 1
f(9kg) = min{f(8kg) + f(1kg), f(1kg) + f(8kg)} = min{2, 2} = 2
f(10kg) = min{f(9kg) + f(1kg), f(2kg) + f(8kg)} = min{3, 3} = 3
f(11kg) = 1
f(12kg) = min{f(11kg) + f(1kg), f(4kg) + f(8kg), f(1kg) + f(11kg)} = min{2, 5, 2} = 2
f(13kg) = min{f(12kg) + f(1kg), f(5kg) + f(8kg), f(2kg) + f(11kg)} = min{3, 6, 3} = 3
f(14kg) = min{f(13kg) + f(1kg), f(6kg) + f(8kg), f(3kg) + f(11kg)} = min{4, 7, 4} = 4
f(15kg) = min{f(14kg) + f(1kg), f(7kg) + f(8kg), f(4kg) + f(11kg)} = min{5, 8, 5} = 5
f(16kg) = min{f(15kg) + f(1kg), f(8kg) + f(8kg), f(5kg) + f(11kg)} = min{6, 2, 6} = 2
f(17kg) = min{f(16kg) + f(1kg), f(9kg) + f(8kg), f(6kg) + f(11kg)} = min{7, 3, 7} = 3

代码实现

const dp = (X) => {
  const result = [];
  for (let x = 0; x <= X; x++) {
    if (x === 0) {
      result[x] = 0;
    } else if (x === 1 || x === 8 || x === 11) {
      result[x] = 1;
    } else if (x < 8) {
      result[x] = result[x - 1] + 1;
    } else if (x < 11) {
      result[x] = Math.min(result[x - 1] + result[1], result[x - 8] + result[8]);
    } else {
      result[x] = Math.min(result[x - 1] + result[1], result[x - 8] + result[8], result[x - 11] + result[11]);
    }
  }
  return result[X];
}
console.log(dp(17)); // 3

示例思考

优化

上述示例中,我们发现 result 表实际上不需要全部保存,每次状态转移计算 f(x) 只需要最多获取历史记录值 f(x - 11),所以我们不需要保存 f(1) ~ f(x - 12) 部分的计算结果。

局限

上述示例中,状态转移函数都是获取历史结果,即砝码重量不存在负数,也就是 f(x) 不存在回溯的情况,否则不再适用。

扩展

针对上述局限,假设我们有一个砝码从异次元拿来,重量为 -1kg,同时我们加入一个 18kg 的砝码同时去掉 8kg的砝码,那么最少需要几个砝码可以获得16kg重量呢?

答案很简单,动态规划结合深度优先搜索即可(部分场景下问题需要结合二分查找)。

和之前的计算逻辑一样,从 x = 0 开始计算 f(x),不同的是,在每个节点 x,我们从该节点出发进行 DFS 搜索,即搜索 +1+11+18-1 五种搜索路径。类似上文,通过状态转移方程依次计算,这里我们需要额外记录下搜索到每个点的步数(也就是砝码数量),当搜索到 x 时,如果记录的搜索步数已经大于当前 f(x) 则返回,因为当前搜索已经不是最优,继续搜索也没有意义了。

代码实现

const dp = (X) => {
  const dir = [1, 11, 18, -1];
  const result = [0];
  const MAXN = 10000;
  // 开始 DFS 搜索,这里不能用递归否则会爆栈
  const dfs = [{ weight: 0, count: 0 }]; // 砝码重量,砝码数量
  while (p = dfs.pop()) {
    for (let i = 0; i < dir.length; i++) {
      const weight = p.weight + dir[i];
      if (weight <= MAXN && weight >= 0) {
        const count = p.count + 1;
        if (result[weight] === void 0 || result[weight] > count) {
          result[weight] = count;
          dfs.push({ weight, count });
        }
      }
    }
  }
  return result[X];
}
console.log(dp(16)); // 3