[TOC] # 简介 动态规划（Dynamic Programming，DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。 <br> 要注意动态规划和分而治之（归并排序和快速排序算法中用到的那种）是不同的方法。分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则是将问题分解成相互依赖的子问题。 另一个例子是上一节解决的斐波那契问题。我们将斐波那契问题分解成如该节图示的小问题。 <br> <br> # 步骤 用动态规划解决问题时，要遵循三个重要步骤： 1. 定义子问题 2. 实现要反复执行而解决子问题的部分（可能是递归） 3. 识别并求解出边界条件 <br> <br> # 分类 能用动态规划解决的一些著名的问题如下： * 背包问题：给出一组项目，各自有值和容量，目标是找出总值最大的项目的集合。这个 问题的限制是，总容量必须小于等于“背包”的容量 * 最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余 下元素的顺序而得到） * 矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少)，相乘操作不会进行，解决方案是找到这些矩阵各自相乘的顺序 * 硬币找零：给出面额为 d1...dn 的一定数量的硬币和要找零的钱数，找出有多少种找零的方法 * 图的全源最短路径：对所有顶点对(u, v)，找出从顶点u到顶点v的最短路径。 <br> <br> # 最少硬币找零 最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可 用的硬币面额 d1...dn 及其数量，找出有多少种找零方法。最少硬币找零问题是给出要找零的钱数， 以及可用的硬币面额 d1...dn 及其数量，找到所需的最少的硬币个数。 <br> 例如，美国有以下面额(硬币）：d1=1, d2=5, d3=10, d4=25，如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（ 1美分)。 <br> 最少硬币找零的解决方案是找到 n 所需的最小硬币数。但要做到这一点，首先得找到对每个 x < n 的解。然后，我们将解建立在更小的值的解的基础上。 <br> 来看看算法： ~~~ class MinCoinChange { constructor(coins) { this.coins = coins this.cache = {} } makeChange(amount) { if (!amount) return [] if (this.cache[amount]) return this.cache[amount] let min = [], newMin, newAmount this.coins.forEach(coin => { newAmount = amount - coin if (newAmount >= 0) { newMin = this.makeChange(newAmount) } if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) { min = [coin].concat(newMin) } }) return (this.cache[amount] = min) } } ~~~ <br> 测试一下算法： ~~~ const minCoinChange = new MinCoinChange([1, 5, 10, 25]) console.log(minCoinChange.makeChange(36)) // [1, 10, 25] const minCoinChange2 = new MinCoinChange([1, 3, 4]) console.log(minCoinChange2.makeChange(6)) // [3, 3]复制代码 ~~~ 所以，找零钱数为6时，最佳答案是两枚价值为3的硬币