从贪婪说起（部分最优）
贪婪算法的基本思路如下：
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...