义乌网站建设zisou8,wordpress中运行程序,手机版网站公司的,做flash音乐网站的开题报告文章目录前言一、零钱兑换II#xff08;力扣518#xff09;二、组合总和 Ⅳ#xff08;力扣377#xff09;三、零钱兑换#xff08;力扣322#xff09;总结前言
1、零钱兑换II 2、组合总和 Ⅳ 3、零钱兑换 一、零钱兑换II#xff08;力扣518#xff09;
给你一个整数…
文章目录前言一、零钱兑换II力扣518二、组合总和 Ⅳ力扣377三、零钱兑换力扣322总结前言
1、零钱兑换II 2、组合总和 Ⅳ 3、零钱兑换 一、零钱兑换II力扣518
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
类似与之前的目标和问题01背包求有多少种组合方式
目标和 分析 题目描述中是凑成总金额的硬币组合数为什么强调是组合数呢 例如示例一 5 2 2 1 5 2 1 2 这是一种组合都是 2 2 1。 如果问的是排列数那么上面就是两种排列了。 组合不强调元素之间的顺序排列强调元素之间的顺序
每个硬币可以重复使用完全背包问题 整数amount 相当于完全背包问题中的背包容量 组合数不强调元素之间的顺序 动规五部曲 1、确定dp数组以及下标的含义 dp[j] 表示总金额为j时有dp[j]种方式 2、确定递推公式 dp[j] dp[j - coins[i]]; 3、dp数组如何初始化 dp[0]一定是1,因为dp[0]是在公式中一切递推结果的起源如果dp[0]是0的话递推结果将都是0。 4、确定遍历顺序 外层for循环遍历物品钱币内层for遍历背包金钱总额组合数 是否可以颠倒 不可以
外层for遍历背包金钱总额内层for循环遍历物品钱币 排列数
class Solution {public int change(int amount, int[] coins) {int[] dp new int[amount1];//初始化 类似于目标和问题dp[0]1;for(int i 0; icoins.length;i){for(int jcoins[i];jamount;j){dp[j] dp[j-coins[i]];}}return dp[amount];}
}二、组合总和 Ⅳ力扣377
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 分析 元素可以重复使用 -- 完全背包问题 求排列数 --遍历顺序 外层循环背包容量 内层循环元素个数
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp new int[target1];dp[0]1;for(int j0;jtarget;j){for(int i 0;inums.length;i){if(j-nums[i]0){dp[j] dp[j-nums[i]]; }}} return dp[target];}
}三、零钱兑换力扣322
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。 分析 每种硬币的数量是无限的可以看出是典型的完全背包问题。 1、确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j] 2、确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j] dp[j] Math.min(dp[j], dp[j-coins[j]]1) 3、dp数组初始化 在测试用例中可以发现 dp[0] 0; 考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。 所以下标非0的元素都是应该是最大值。 4、确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。 所以本题并不强调集合是组合还是排列。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];int max Integer.MAX_VALUE;//初始化为最大值for(int i0;idp.length;i){dp[i] max;}dp[0] 0;//遍历for(int i0;icoins.length;i){for(int jcoins[i];jamount;j){if(dp[j-coins[i]]!max){dp[j] Math.min(dp[j],dp[j-coins[i]]1);}}}return dp[amount] max? -1:dp[amount];}
}总结
如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品
