网站建设软件kan,js wordpress 菜单管理,wordpress前端用什么,做家常菜网站题意理解#xff1a; 给你一个整数数组 coins 表示不同面额的硬币#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额#xff0c;返回 0 。 将coins看作不同重量的背包#xff0c;然后把要凑成的组… 题意理解 给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。 将coins看作不同重量的背包然后把要凑成的组合数看作背包容量。 则该问题就是一个完全背包问题 即使用重量为coins的物品每个物品有无数个装满大小为amount的背包有多少种装法。 解题思路 首先理解题意将题目转换为完全背包问题。 其中递归函数为 dp[j]表示凑满target有n种方式 for(int i0;icoins.length;i) dp[j]dp[j-coins[i]] 关于遍历顺序 1.遍历顺序问题 比如amount3 coins[1,2] 先目硬币后目标值
public int change22(int amount, int[] coins) {//dp[target]数组表示凑出target,有dp[target]种方法int[] dpnew int[amount1];Arrays.fill(dp,0);dp[0]1;for(int i0;icoins.length;i){for(int target0;targetamount;target){System.out.println(target:target);if(targetcoins[i]){System.out.print(硬币:coins[i]\t\t);dp[target]dp[target-coins[i]];}print(dp);}}return dp[amount];} target:0 1 0 0 0 target:1 硬币:1 1 1 0 0 target:2 硬币:1 1 1 1 0 target:3 硬币:1 1 1 1 1 target:0 1 1 1 1 target:1 1 1 1 1 target:2 硬币:2 1 1 2 1 target:3 硬币:2 1 1 2 2 2 其中target0时有一种方式没有一个硬币 target1时一种方式一个硬币 1 target2时两种方式 11 2 target3时两种方式 111 21|12 所以可以看出这里先硬币后目标值是组合数所以12 和21 是同一个方式 先目标值后硬币
public int change(int amount, int[] coins) {//dp[target]数组表示凑出target,有dp[target]种方法int[] dpnew int[amount1];Arrays.fill(dp,0);dp[0]1;for(int target0;targetamount;target){System.out.println(target:target);for(int i0;icoins.length;i){if(targetcoins[i]){System.out.print(硬币:coins[i]\t\t);dp[target]dp[target-coins[i]];}}print(dp);}return dp[amount];} target:0 1 0 0 0 target:1 硬币:1 1 1 0 0 target:2 硬币:1 硬币:2 1 1 2 0 target:3 硬币:1 硬币:2 1 1 2 3 3 其中凑出target0,有一种方式一个硬币也没有 凑出target1,有一种方式有一个硬币 凑出target2有两种方式 11 2 凑出target3有三种方式 111 21 12 所以可以得出先目标值后硬币是排序数21 和12是两种方式 总结 先硬币后目标值组合数 先目标值后硬币排序数 先遍历硬币后遍历目标值对于3来说 dp[3]dp[2]dp[1] 使用硬币1 111 一种方式 dp[2]1,当且仅当仅有硬币1的时候凑成3有一种方式 使用硬币2 21 一种方式 dp[1]1,当且仅当仅有硬币1和2的时候时放入2只有21一种方式凑成3 先遍历目标值后遍历硬币时对于3来说 dp[3]dp[2]dp[1] dp[2]2 其中 11 2—— 111 21 dp[1]1 其中 1 ——12 2.求解 public int change(int amount, int[] coins) {//dp[target]数组表示凑出target,有dp[target]种方法int[] dpnew int[amount1];Arrays.fill(dp,0);dp[0]1;for(int i0;icoins.length;i){for(int target0;targetamount;target){if(targetcoins[i]){dp[target]dp[target-coins[i]];}}}return dp[amount];}
3.分析 时间复杂度 O(n^2) 空间复杂度 O(n)
