共计 5078 个字符，预计需要花费 13 分钟才能阅读完成。
从贪婪说起（部分最优）
贪婪算法的基本思路如下：
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…
正文完