网站建设教程免费下载,烟台百度网站推广,清远网站设计公司,做外贸网站机构题目
322. 零钱兑换
中等
相关标签
广度优先搜索 数组 动态规划
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组…题目
322. 零钱兑换
中等
相关标签
广度优先搜索 数组 动态规划
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。 示例 1
输入coins [1, 2, 5], amount 11输出3解释11 5 5 1
示例 2
输入coins [2], amount 3输出-1
示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 231 - 10 amount 104
思路和解题方法 目标和的定义这个问题的目标是计算凑出目标金额所需的最少硬币数量。 动态规划的思路该代码使用了动态规划的思想将原问题拆解为子问题并利用已解决的子问题的解来求解更大规模的问题。 dp 数组的定义代码创建了一个大小为 amount1 的 dp 数组用于保存计算中间状态的结果。dp[i] 表示组成金额 i 所需的最少硬币数量。 初始化将 dp[0] 初始化为 0表示组成金额为 0 不需要任何硬币。其他位置的 dp 数组元素初始化为 INT_MAX表示初始时无法凑出对应的金额。 状态转移方程采用两层循环来遍历物品和背包。外层循环遍历所有可用的硬币面额内层循环遍历目标金额从该硬币面额开始到 amount。这样可以逐步更新 dp 数组计算得到凑出每个目标金额所需的最少硬币数量。 状态转移对于当前的目标金额 j我们检查 dp[j - coins[i]] 是否不是初始值 INT_MAX。如果不是初始值则表示可以通过使用当前硬币面额 coins[i] 得到目标金额 j。我们比较使用当前硬币和不使用当前硬币两种情况下所需的硬币数量并取最小值作为 dp[j] 的解。 返回结果最后我们返回 dp[amount] 的值作为结果。如果 dp[amount] 仍为初始值 INT_MAX表示无法凑出目标金额因此返回 -1。 总结起来这段代码使用动态规划的思想通过构建一个 dp 数组来保存计算中间状态的结果。通过遍历物品和背包并利用已解决子问题的解逐步计算得到组成目标金额所需的最少硬币数量。最终返回 dp[amount] 的值作为结果。 复杂度 时间复杂度: O(n * amount) 时间复杂度 外层循环遍历硬币列表的长度即 coins 的大小所以时间复杂度为 O(n)其中 n 是硬币列表的长度。内层循环遍历目标金额 amount所以时间复杂度为 O(amount)。 综合起来总的时间复杂度为 O(n * amount)。 空间复杂度 O(amount) 空间复杂度 创建了一个大小为 amount1 的 dp 数组所以空间复杂度为 O(amount)。 因此该算法的空间复杂度为 O(amount)。 c 代码
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX); // 创建大小为 amount1 的 dp 数组初始值设置为 INT_MAXdp[0] 0; // 对于组成金额为 0 的情况方法数为 0for (int i 0; i coins.size(); i) { // 遍历每个硬币面额物品for (int j coins[i]; j amount; j) { // 遍历每个目标金额背包if (dp[j - coins[i]] ! INT_MAX) { // 如果 dp[j - coins[i]] 不是初始值即存在组合方式dp[j] min(dp[j - coins[i]] 1, dp[j]); // 更新组成金额 j 的最小方法数}}}if (dp[amount] INT_MAX) return -1; // 如果无法组成金额 amount则返回 -1 表示无解return dp[amount]; // 返回组成金额 amount 的最小方法数}
};vectorint dp(amount 1, INT_MAX);创建大小为 amount1 的 dp 数组用于保存组成不同金额的最小硬币数。初始值设置为 INT_MAX表示初始状态下无解。dp[0] 0;对于金额为 0 的情况不需要使用任何硬币所以最小硬币数为 0。for (int i 0; i coins.size(); i)外层循环遍历硬币面额物品以便逐个考虑每个硬币的组合方式。for (int j coins[i]; j amount; j)内层循环遍历目标金额背包从当前硬币面额开始直到目标金额 amount。这样可以确保只考虑能够达到的金额。if (dp[j - coins[i]] ! INT_MAX)如果 dp[j - coins[i]] 不是初始值即存在组合方式则进入条件判断。dp[j] min(dp[j - coins[i]] 1, dp[j]);更新组成金额 j 的最小硬币数。在当前硬币面额 coins[i] 的情况下组成金额 j 的最小硬币数为 dp[j - coins[i]] 1 和当前 dp[j] 的较小值。if (dp[amount] INT_MAX) return -1;如果无法组成金额 amount则返回 -1 表示无解。return dp[amount];返回组成金额 amount 的最小硬币数。 Java代码
class Solution {public int coinChange(int[] coins, int amount) {int max Integer.MAX_VALUE;int[] dp new int[amount 1];//初始化dp数组为最大值for (int j 0; j dp.length; j) {dp[j] max;}//当金额为0时需要的硬币数目为0dp[0] 0;for (int i 0; i coins.length; i) {//正序遍历完全背包每个硬币可以选择多次for (int j coins[i]; j amount; j) {//只有dp[j-coins[i]]不是初始最大值时该位才有选择的必要if (dp[j - coins[i]] ! max) {//选择硬币数目最小的情况dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount] max ? -1 : dp[amount];}
} 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
