关于javascript:从-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/col…
• https://leetcode-cn.com/probl…
• https://github.com/shanejix/a…
• https://github.com/shanejix/a…