题解 | #兑换零钱(一)#
兑换零钱(一)
http://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
所以我们可以这样定义 dp 函数：dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。
const dp = (coins,amount) =>{
if(amount === 0) return 0;
if(amount < 0) return -1;
let res = Number.MAX_VALUE;
for(let coin of coins){
// 计算子问题的结果
let subProblem = dp(coins, amount - Number(coin));
// 子问题无解则跳过
if(subProblem === -1)continue;
res = Math.min(res,subProblem + 1);// 在子问题中选择最优解，然后加一
}
return res === Number.MAX_VALUE ? -1 : res;
}
function minMoney( arr , aim ) {
return dp(arr,aim)
}
子问题总数为递归树的节点个数，但算***进行剪枝，剪枝的时机和题目给定的具体硬币面额有关，所以可以想象，这棵树生长的并不规则，确切算出树上有多少节点是比较困难的。对于这种情况，我们一般的做法是按照最坏的情况估算一个时间复杂度的上界。
假设目标金额为 n，给定的硬币个数为 k，那么递归树最坏情况下高度为 n（全用面额为 1 的硬币），然后再假设这是一棵满 k 叉树，则节点的总数在 k^n 这个数量级。
接下来看每个子问题的复杂度，由于每次递归包含一个 for 循环，复杂度为 O(k)，相乘得到总时间复杂度为 O(k^n)，指数级别。
2、带备忘录的递归let memo = [];
const dp = (coins,amount) =>{
if(amount === 0) return 0;
if(amount < 0) return -1;
// 查备忘录，防止重复计算
if(memo[amount] !== -666)return memo[amount];
let res = Number.MAX_VALUE;
for(let coin of coins){
// 计算子问题的结果
let subProblem = dp(coins, amount - Number(coin));
// 子问题无解则跳过
if(subProblem === -1)continue;
// 在子问题中选择最优解，然后加一
res = Math.min(res,subProblem + 1);
}
// 把计算结果存入备忘录
memo[amount] = res === Number.MAX_VALUE ? -1 : res;
return memo[amount];
}
function minMoney( arr , aim ) {
memo = Array(aim+1).fill(-666);
return dp(arr,aim)
}
很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。
function minMoney( arr , aim ) {
let dp = Array(aim+1).fill(aim+1);// 数组大小为 amount + 1，初始值也为 amount + 1
dp[0] = 0;
// 外层 for 循环在遍历所有状态的所有取值
for(let i=0;i <dp.length; i++){
// 内层 for 循环在求所有选择的最小值
for(let coin of arr){
if(i - coin < 0){
continue;
}// 子问题无解，跳过
dp[i] = Math.min(dp[i],1 + dp[i -Number(coin)])
}
}
return (dp[aim] === aim +1) ? -1 : dp[aim];
}
function minMoney( arr , aim ) {
let dp = new Array(aim + 1).fill(Infinity);// 初始化dp数组
dp[0] = 0;// 面额0只需要0个硬币兑换
for (let i = 1; i <= aim; i++) {// 循环面额
for (let coin of arr) {// 循环硬币数组
if (i - coin >= 0) {// 当面额大于硬币价值时
// dp[i - coin]： 当前面额i减当前硬币价值所需要的最少硬币
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[aim] === Infinity ? -1 : dp[aim];
}
module.exports = {
minMoney : minMoney
};
PS：为啥 dp 数组中的值都初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢？因为后面有 dp[i - coin] + 1，这就会导致整型溢出。
投递美团等公司10个岗位 >