有没有人与动物做的电影网站,wordpress归档,简书wordpress,云南企业展厅设计公司上次分享完完全背包问题的解决思路后#xff0c;这次分享一道和完全背包有关的leetcode题。
零钱兑换 给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果… 上次分享完完全背包问题的解决思路后这次分享一道和完全背包有关的leetcode题。
零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。 示例 1 输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount 1];for(int i 1;i amount;i){dp[i] Integer.MAX_VALUE;}dp[0] 0;for(int i 0;i coins.length;i){for(int j 0;j amount;j){if(j coins[i] dp[j - coins[i]] ! Integer.MAX_VALUE){dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount] Integer.MAX_VALUE ? -1 : dp[amount];}
}这道题和完全背包问题相同点就是硬币的数量是无限的可以重复使用不同的是完全背包问题是使得背包里面物品的价值最大不一定要装满背包这道题则是恰好装满背包要求使用的物品数量最少。解决思路也是装与不装不装则是dp[j]装的话背包容量就需要减去物品重量此时加上的不再是物品的价值而是物品的数量仅装入一个物品物品数加1要求硬币数量最少所以要取最小值。这里有一个需要强调的点就是dp数组的初始化问题对于这种要求恰好装满背包求最值的问题dp数组的初始化首元素一般都是0其次其余元素就需要看要求的是最大值还是最小值这里要求物品数量最少所以其余元素初始化为整数最大值。在上一篇的完全背包问题时遇到恰好装满背包背包价值最大这是dp首元素为0其余元素则初始化为整数最小值。 这里以上述示例说明代码的执行流程。这里钱币的面值即是物品的体积也是物品的价值面值有12和5总金额为11所以dp数组初始化为11。dp数组如下所示dp[j]的含义是金额为j需要的最小硬币数量为dp[j] 之后遍历面值1当背包容量j(总金额)为0时不满足j coins[0]不进入if背包容量j(总金额)为1时j coins[0]并且j - coins[0] 0可以装下dp[1] min(dp[j], dp[j - coins[i]] 1) dp[0] 1 1。这里就很好的说明为什么dp[0]为什么要初始化为0不初始化为0对结果有影响而且dp[1]要初始化为整数最大值如果初始化为别的数如0的话这里得到的结果就不是1而是0所以其余dp元素要初始化为整数最大值。背包容量j(总金额)为2时dp[2] min(dp[2], dp[j - coins[i]] 1) dp[2 - coins[0]] 1 dp[1] 1 1 1 2dp[3] dp[2] 1 3如此重复遍历完面值1dp数组如下 之后遍历面值2当背包容量j(总金额)为0和1时不满足j coins[1]保持原值当j等于2时j coins[1]dp[2] min(dp[2]dp[j - coins[1]] 1) min(2, dp[0] 1) 1用于dp是一维滚动数组因此dp[2]的值是1现在遍历面值2时dp[2]为1接着j 3dp[3] min(3dp[3 - 2] 1) dp[1] 1 2dp[4] min(4, dp[4 - 2] 1) dp[2] 1 1 1 2此时的dp[2]为1在j 2时修改了dp[2]的值。dp[5] min(5, dp[5 - 2] 1) dp[3] 1 3dp[6] 3如此重复遍历得到dp数组如下 之后遍历面值5当当背包容量j(总金额)为01234时不满足j coins[1]保持原值j等于5dp[5] min(3, dp[5 - 5] 1) 1dp[6] min(3, dp[6 - 5] 1) 1 1 2如此重复得到dp数组如下这里就不再展开说明遍历完所有面值返回dp[11]即为最终结果。
