Shane Jix

从 0 到 1 入门动态规划

create:August 14, 2021  update:April 12, 2022  ☕️☕️ 8 min read

同步链接: 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

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

Edit on GitHubDiscuss on GitHub


Shane Jix

Personal blog by Shane Jix. I explain with words and code.

LinksTools
© 2019 - 2022, Built withGatsby