Dynamic Programming

[shanejix]

同步链接: https://www.shanejix.com/posts/从 0 到 1 入门动态规划/

从贪心说起（局部最优）

贪心算法的基本思路如下：

1. 将待求解问题分解为若干子问题，分别对子问题求解得到子问题的局部最优解

2. 将子问题的局部最优解的进行合并，得到基于局部最优解的结果

所谓贪心就是着眼于当下（局部）的最优结果，而不从整体（全局）出发考虑。两种思路分别对应局部最优解和整体最优解

可以看出，贪心的局部最优整合的结果往往不是全局的最优解！例如：322. 零钱兑换

问题：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

按照 贪心的思路 通过从大到小枚举所有硬币面值，应该优先尽可能多的使用面值大的硬币，这样用掉的硬币数量才会尽可能的少！代码如下

// 🎨 方法一：贪心算法

// 📝 思路：贪心得到局部最优，但肯能不是整体最优，因此存在用例不过

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  let rest = amount;
  let count = 0;

  coins.sort((a, b) => b - a);

  // 从大到小遍历面值
  for (let coin of coins) {
    // 计算当前面值能用多少个
    let currCount = Math.floor(rest / coin);
    // 累加当前面额使用数量
    count += currCount;
    // 使用当前面值后更新剩余面值
    rest -= coin * currCount;

    if (rest === 0) {
      return count;
    }
  }

  return -1;
};

贪心不适合所有问题（有的用例是不通过），正是因为有时太贪了！例如：

从 coins[0]=5, coins[1]=3 且 k=11 的情况下寻求最少硬币数

按照“贪心思路”，先挑选面值最大的，即为 5 的硬币放入钱包。接着，还有 6 元待解（即 11-5 = 6）。这时，再次“贪心”，放入 5 元面值的硬币。这个时候就只剩下 1 元了，再放入 5 就不能刚刚凑整 11 元。但其实这个问题是有解的（5 + 3 + 3 = 11）。

这就是过度贪心导致的问题，可以通过回溯解决，正如同：电梯超负荷了下去个胖子上来个瘦子

// 🎨 方法二：回溯 + 递归

// 📝 思路：用例没通过

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // 组合硬币的数量
  let res = Infinity;

  coins.sort((a, b) => b - a);

  if (coins.length === 0) {
    return -1;
  }

  /**
   * 从当前组合中求最小硬币数量
   * @param {*} coins
   * @param {*} total
   * @param {*} index
   * @returns
   */
  const getMinCoinCountOfValue = (coins, total, index) => {
    if (index === coins.length) {
      return Infinity;
    }

    let minResult = Infinity;
    let currValue = coins[index];
    let maxCount = Math.floor(total / currValue);

    for (let count = maxCount; count >= 0; count--) {
      let rest = total - count * currValue;

      if (rest === 0) {
        minResult = Math.min(minResult, count);
      }

      let restCount = getMinCoinCountOfValue(coins, rest, index + 1);

      if (restCount === Infinity) {
        if (count === 0) {
          break;
        }
        continue;
      }

      minResult = Math.min(minResult, count + restCount);
    }

    return minResult;
  };

  /**
   * 求所有满足条件的组合
   * @param {*} coins
   * @param {*} amount
   * @param {*} index
   */
  const getMinCoinCount = (coins, amount, index) => {
    // 递归终止的条件
    if (index === coins.length) {
      // getMinCoinCountOfValue() 对重新排序后的coins求最小硬币数量
      res = Math.min(res, getMinCoinCountOfValue(coins, amount, 0));
    }

    for (let i = index; i < coins.length; i++) {
      // swap
      [coins[index], coins[i]] = [coins[i], coins[index]];
      // 做出选择
      res = Math.min(res, getMinCoinCount(coins, amount, index + 1))[
        // 回溯 撤销选择
        (coins[index], coins[i])
      ] = [coins[i], coins[index]];
    }
  };

  getMinCoinCount(coins, amount, 0);

  // 没有任意的硬币组合能组成总金额，则返回 -1
  return res === Infinity ? -1 : res;
};

其实，方法二中回溯递归的算和方法一中的枚举本质上都是枚举问题：枚举出所有问题，从中选择最优解

递归的过程其实可以等同出一棵递归树，如果遍历完整棵树（枚举所有情况）时间复杂度非常高（指数级），并且遍历时存在大量的重叠子问题（可以参考画出著名的求斐波那契数列递归的解法的递归树）。因此有时需要通过条件进行剪枝优化。

贪心正是322. 零钱兑换方法二中递归的剪枝优化思路。对应递归树中最短路径，但最短路径往往不是所求得的解，因此需要回溯遍历其他路径。相比较枚举完所有情况能节省不少复杂度。

重叠子问题（记忆化搜索）

为了消除普遍存在的重复子问题，需要采用另外的思路来进行优化，普遍使用的手段时状态存储或记忆化搜索 memorization

例如：322. 零钱兑换

// 🎨 方法三：递归 + 记忆化搜索

// 📝 思路：枚举存在大量重复，用memo缓存重复计算的值

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // 组合硬币的数量
  let res = Infinity;
  // 缓存重复计算的值,memo[total] 表示币值数量为 total 可以换取的最小硬币数量，没有缓存则为 -2
  const memo = new Array(amount + 1).fill(-2);

  // 0 对应的结果为 0
  memo[0] = 0;

  coins.sort((a, b) => b - a);

  if (coins.length === 0) {
    return -1;
  }

  /**
   * 找到 total 数量零钱可以兑换的最少硬币数量
   * @param {*} coins
   * @param {*} total
   * @returns
   */
  const getMinCoinCount = (coins, total) => {
    // 递归终止的条件
    if (total < 0) {
      return -1;
    }

    // 递归终止的条件
    if (total === 0) {
      return 0;
    }

    // 先从缓存中查找 memo[total]
    if (memo[total] !== -2) {
      return memo[total];
    }

    let minCount = Infinity;

    // 遍历所有面值
    for (let i = 0; i < coins.length; i++) {
      // 如果当前面值大于总额则跳过
      if (coins[i] > total) {
        continue;
      }

      // 使用当前面额，并求剩余总额的最小硬币数量
      let restCount = getMinCoinCount(coins, total - coins[i]);

      if (restCount === -1) {
        // 当前选择的coins[i] 组合不成立，跳过
        continue;
      }

      // 更新最小总额
      let totalCount = 1 + restCount;
      if (totalCount < minCount) {
        minCount = totalCount;
      }
    }

    // 如果没有可用组合，返回 -1
    if (minCount === Infinity) {
      memo[total] = -1;
      return -1;
    }

    // 更新缓存
    memo[total] = minCount;
    return minCount;
  };

  return getMinCoinCount(coins, amount);
};

记忆化搜索是自顶向下递归的过程，将大问题不断的拆解成小问题，然后对小问题逐个求解。递归很直观，但是存在性能问题（基于栈，产生额外的时间和空间开销）和难调试等问题。

迭代和动态规划

为了规避递归（记忆化搜索）的缺点可以，可以将自顶向下的递归实现转化为自底向上的迭代实现。

如果在预知处理每个大问题前必须处理那些小问题，那么就可以先求解所有的小问题的解再求解大问题的解，这就是自底向上的过程。

如果子问题的依赖关系是单向的，（a 依赖于 b ，但是 b 不直接或间接依赖于 a），那么就可以直接自底向上求解。

// 🎨 方法五：动态规划

// 📝 思路：自底向上，记忆化化搜索

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // memo[total] 表示币值数量为 total 可以换取的最小硬币数量，没有缓存则为 -1
  const memo = new Array(amount + 1).fill(-1);
  // 初始化状态
  memo[0] = 0;

  // 币值总额状态从 1 到 amount
  for (let v = 1; v <= amount; v++) {
    // 当前币值总额 v 对应的能凑齐最小硬币数量
    let minCount = Infinity;

    // 对当前币值总额 v 枚举所有的 硬币面值
    for (let i = 0; i < coins.length; i++) {
      let currValue = coins[i];

      // 如果当前面值大于币值总额，跳过
      if (currValue > v) {
        continue;
      }

      // 使用当前面值，得到剩余币值总额
      let rest = v - currValue;
      // 从缓存中取出剩余币值总额对应的最小硬币数量
      let restCount = memo[rest];

      // -1 则表示 组合不成立 跳过
      if (restCount == -1) {
        continue;
      }

      // 当前币值组合成立
      let currCount = 1 + restCount;

      // 更新当前币值总额 v 的最小硬币数量
      if (currCount < minCount) {
        minCount = currCount;
      }
    }

    // 当前币值总额 v 的最小硬币数量若存在则缓存
    if (minCount !== Infinity) {
      memo[v] = minCount;
    }
  }

  return memo[amount];
};

没错，这种通过迭代实现的记忆化搜索的求解过程就是动态规划

动态规划特征

标准的动态规划一般包含下面三个特征

- 重叠子问题：在枚举过程中存在重复计算的现象（如斐波那契数列递归实现）


- 最优子结构：子问题之间必须相互独立，后续的计算可以通过前面的状态推导出来


- 无后效性：子问题之间的依赖是单向性的，已经确定的状态不会受到后续决策的影响

通用动态规划解题框架

动态规划的核心是 状态转移方程 ，需要确定以下几点

- 状态（状态参数）：子问题和原问题之间会发生变化的量（状态变量）

- 状态存储 memo ： 根据状态参数 定义 dp[i]...[j] 的含义

- 初始化状态：需要一个“原点”最为计算的开端（从已经计算好的子问题推广到更大的问题上）

- 决策和状态转移：改变状态，让状态不断逼近初始化状态的行为

以上是解决动态规划的整体思路，若要灵活运用还需熟练各类经典的动态规划题目，见 分类列表

references

• https://time.geekbang.org/column/intro/100060501
• https://leetcode-cn.com/problems/coin-change/
• https://github.com/shanejix/algorithm-and-data-structure
• https://github.com/shanejix/algorithm-and-data-structure/blob/master/pattern/dynamic-programming/0322.CoinChange.js

作者：shanejix
出处：https://www.shanejix.com/posts/从 0 到 1 入门动态规划/
版权：本作品采用「署名-非商业性使用-相同方式共享 4.0 国际」许可协议进行许可。
声明：转载请注明出处！