动态规划凑零钱问题

动态规划特点：

1. 重复子问题
2. 状态转移方程（最关键）
3. 最优子结构
   题型：求最值
   核心： 穷举

解题套路：

1. 明确状态
2. 明确选择
3. 明确dp函数/数组的定义
4. 明确base case

# 暴力求解(超时，通过不了)
class Solution {// 状态：目标金额 amount// 选择：coins 数组中列出所有硬币面额// 函数的定义：凑出总金额amount，至少需要coinChange(coins,amount)枚硬币// base case： amount = 0时，需要0枚硬币；amount<0时，不可能凑出// coinChage([1,2,5],11)// = 1 + min(coinChage([1,2,5],10),coinChage([1,2,5],9,coinChage([1,2,5],6))int[] memo;public int coinChange(int[] coins, int amount) {// base caseif(amount==0) return 0;if(amount<0) return -1;int res = Integer.MAX_VALUE;for(int coin : coins){// 计算子问题的结果int subProblem = coinChange(coins,amount-coin);if(subProblem==-1) continue;// 在子问题中选择最优解，然后加1res = Math.min(res,subProblem+1);}// 在最后一步还要判断res是否有变化return res == Integer.MAX_VALUE?-1:res;}}

class Solution {// 状态：目标金额 amount// 选择：coins 数组中列出所有硬币面额// 函数的定义：凑出总金额amount，至少需要coinChange(coins,amount)枚硬币// base case： amount = 0时，需要0枚硬币；amount<0时，不可能凑出// coinChage([1,2,5],11)// = 1 + min(coinChage([1,2,5],10),coinChage([1,2,5],9,coinChage([1,2,5],6))int[] memo;int coinChange(int[] coins, int amount) {memo = new int[amount + 1];// 备忘录初始化为一个不会被取到的特殊值，代表还未被计算Arrays.fill(memo, -666);return dp(coins, amount);
}int dp(int[] coins, int amount) {if (amount == 0) return 0;if (amount < 0) return -1;// 查备忘录，防止重复计算if (memo[amount] != -666)return memo[amount];int res = Integer.MAX_VALUE;for (int coin : coins) {// 计算子问题的结果int subProblem = dp(coins, amount - coin);// 子问题无解则跳过if (subProblem == -1) continue;// 在子问题中选择最优解，然后加一res = Math.min(res, subProblem + 1);}// 把计算结果存入备忘录memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;return memo[amount];
}
}

# 自底向上：
class Solution {// 状态：目标金额 amount// 选择：coins 数组中列出所有硬币面额// 函数的定义：凑出总金额amount，至少需要coinChange(coins,amount)枚硬币// base case： amount = 0时，需要0枚硬币；amount<0时，不可能凑出// coinChage([1,2,5],11)// = 1 + min(coinChage([1,2,5],10),coinChage([1,2,5],9,coinChage([1,2,5],6))public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];// dp数组全部初始化为特殊值 amount + 1Arrays.fill(dp,amount+1);// dp数组的定义：凑出总金额amount，至少需要dp[amount]枚硬币// base casedp[0] = 0;// 外层for循环在遍历所有状态的所有取值for(int i=0;i<dp.length;i++){// 内层for循环在求所有选择的最小值for(int coin:coins){if(i-coin<0) continue;// 状态转移dp[i] = Math.min(dp[i],1+dp[i-coin]);}}//查看金额amount能不能凑出来return (dp[amount] == amount + 1)?-1:dp[amount];}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！