动态规划(dynamic programming, DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。
用动态规划解决问题时,要遵循三个重要步骤:
(1) 定义子问题;
(2) 实现要反复执行来解决子问题的部分;
(3) 识别并求解出基线条件。
动态规划解决 最少硬币找零问题
最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数,以及可用的硬币面额d 1,…, dn及其数量,找出有多少种找零方法。最少硬币找零问题是给出要找零的钱数,以及可用的硬币面额d1,…, dn及其数量,找到所需的最少的硬币个数。
例如,美国有以下面额(硬币):d1= 1, d2= 5, d3= 10, d4= 25。如果要找36美分的零钱,我们可以用1个25美分、1个10美分和1个便士(1美分)。
如何将这个解答转化成算法?
下面来看看算法。
function minCoinChange(coins, amount) {
const cache = []; // {1}
const makeChange = (value) => { // {2}
if (! value) { // {3}
return [];
}
if (cache[value]) { // {4}
return cache[value];
}
let min = [];
let newMin;
let newAmount;
for (let i = 0; i < coins.length; i++) { // {5}
const coin = coins[i];
newAmount = value - coin; // {6}
if (newAmount >= 0) {
newMin = makeChange(newAmount); // {7}
}
if (
newAmount >= 0 && // {8}
(newMin.length < min.length -1 || ! min.length) && // {9}
(newMin.length || ! newAmount) // {10}
) {
min = [coin].concat(newMin); // {11}
console.log('new Min ' + min + ' for ' + amount);
}
}
return (cache[value] = min); // {12}
};
return makeChange(amount); // {13}
}
minCoinChange参数接收coins参数(行{1}),该参数代表问题中的面额。对美国的硬币系统而言,它是[1, 5, 10, 25]。我们可以随心所欲地传递任何面额。此外,为了更加高效且不重复计算值,我们使用了cache(行{1}——这个技巧称为记忆化)。
接下来是minCoinChange函数中的makeChange方法(行{2}),它也是一个递归函数,用来解决问题。makeChange函数在行{13}被调用,amount作为参数传入。由于makeChange是一个内部函数,它也能访问到cache变量。
现在我们来看算法的主要逻辑。首先,若amount不为正(< 0),就返回空数组(行{3});方法执行结束后,会返回一个数组,包含用来找零的各个面额的硬币数量(最少硬币数)。接着,检查cache缓存。若结果已缓存(行{4}),则直接返回结果;否则,执行算法。
为了进一步帮助我们,我们基于coins参数(面额)解决问题。因此,对每个面额(行{5}),我们都计算newAmount(行{6})的值,它的值会一直减小,直到能找零的最小钱数(别忘了本算法对所有的x < amount都会计算makeChange结果)。若newAmount是合理的值(正值),我们也会计算它的找零结果(行{7})。
最后,我们判断newAmount是否有效,minValue(最少硬币数)是否是最优解,与此同时minValue和newAmount是否是合理的值(行{10})。若以上判断都成立,意味着有一个比之前更优的答案(行{11}——以5美分为例,可以给5便士或者1个5美分镍币,1个5美分镍币是最优解)。最后,返回最终结果(行{12})。
测试一下这个算法。
console.log(minCoinChange([1, 5, 10, 25], 36));
要知道,如果我们检查cache变量,会发现它存储了从1到36美分的所有结果。以上代码的结果是[1, 10, 25]。
网友评论