首页 > 其他分享 >每日一题:Leetcode-322 零钱兑换

每日一题:Leetcode-322 零钱兑换

时间:2024-07-23 13:27:47浏览次数:16  
标签:硬币 int coins 示例 322 零钱 amount Leetcode dp

力扣题目

解题思路

java代码

力扣题目:

给你一个整数数组 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

解题思路:

解法思路

  • 首先创建一个长度为 amount + 1 的整数数组 dp ,用于保存每个金额对应的最少硬币数。
  • 初始化 dp[0] = 0 ,表示凑出金额为 0 不需要硬币。对于其他金额 i ,先初始化为 Integer.MAX_VALUE ,表示暂时无法凑出。
  • 然后通过两层循环来计算每个金额的最少硬币数。外层循环遍历每个金额 i ,内层循环遍历每种面额的硬币 coins[j] 。
  • 如果当前金额 i 大于等于硬币面额 coins[j] ,就尝试更新 dp[i] ,取当前值和使用该硬币后(dp[i - coins[j]] + 1)的较小值。

java代码:

package org.example.mouth7.today23;

public class Leetcode322 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));
    }
    public static 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 = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j]) {
                    dp[i] = Math.min( dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

更多详细内容同步到公众号,感谢大家的支持!

每天都会给刷算法的小伙伴推送明日一题,并且没有任何收费项

标签:硬币,int,coins,示例,322,零钱,amount,Leetcode,dp
From: https://blog.csdn.net/LIUCHANGSHUO/article/details/140625501

相关文章

  • 1322、基于51单片机氨气温度土壤湿度检测加热浇水等控制设计(程序+原理图+元器件清单+
    毕设帮助、开题指导、技术解答(有偿)见文未  目录方案选择单片机的选择显示器选择方案一、设计功能二、实物图单片机模块设计三、原理图四、程序源码资料包括:需要完整的资料可以点击下面的名片加下我,找我要资源压缩包的百度网盘下载地址及提取码。方案选择单片......
  • 【代码随想录训练营第42期 Day6打卡 LeetCode 242.有效的字母异位词 349.两个数组的交
    目录一、序言二、哈希表的相关知识1.基本概念2.常见的哈希结构3.总结三、题目及其题解242.有效的字母异位词题目链接题解思路1思路2思路3349.两个数组的交集题目链接题解202.快乐数题目链接题解1.两数之和题目链接题解思路1思路2四、小结一、序言......
  • 代码随想录算法训练营第一天leetcode704二分查找27移除元素
    leetcode704,这是leetcode提交四次后通过的结果:classSolution{  publicintsearch(int[]nums,inttarget){    if(nums.length==1&&nums[0]==target)      return 0;    if(nums.length==2)      if(nums[0]==target)......
  • Array Sum up increment. 1526, 3229
    1526.MinimumNumberofIncrementsonSubarraystoFormaTargetArrayYouaregivenanintegerarray target.Youhaveanintegerarray initial ofthesamesizeas target withallelementsinitiallyzeros.Inoneoperationyoucanchoose any subarray......
  • LeetCode 3070. 元素和小于等于 k 的子矩阵的数目
    3070.元素和小于等于k的子矩阵的数目给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的数目。示例1:输入:grid=[[7,6,3],[6,6,1]],k=18输出:4解释:如上图所示,只有4个子矩阵满足:包含g......
  • leetcode位运算(1684. 统计一致字符串的数目)
    前言经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。后续开始专项练习。描述实现原理与步骤1.本题重点掌握相应字符bit位的编码规则2.bitArray和tempBitArray或之后还等于bitArray,说明bitArray包含tempBitArray代码实现classSolution{publ......
  • LeetCode题(66,69,35,88)--《c++》
     66.加一////Createdbywxj05on2024/7/20.////法一classSolution{public:vector<int>plusOne(vector<int>&digits){boolcarry=true;//进位标志for(inti=digits.size()-1;i>=0&&carry;--i){......
  • Leetcode2427. 公因子的数目和Leetcode.728. 自除数
    Leetcode2427问题描述:给你两个正整数 a 和 b ,返回 a 和 b 的 公 因子的数目。如果 x 可以同时整除 a 和 b ,则认为 x 是 a 和 b 的一个 公因子 。示例1:输入:a=12,b=6输出:4解释:12和6的公因子是1、2、3、6。示例2:输入:a=25,b=30......
  • leetcode 224 基本计算器
    题面就是实现一个字符串输入的加减法计算器(带括号),注意一元的减号是会出现的,且字符串中有空格思路就是使用两个栈,一个储存数字和计算结果,另外一个存运算符。基本步骤删去括号如果遇到')'就开始计算直到前一个左括号,运算顺序是先出栈的放在后面遇到的坑减号的优先级是高的,......
  • Leetcode 中的动态规划
    对于初学者来说,Leetcode中的动态规划可以做哪些问题?我想知道可以使用Leetcode中的动态规划来解决哪些问题,对于初学者来说很容易。我一直在LeetCode上练习问题,我注意到有些问题被专门标记为“动态编程”(DP)。我了解DP的基础知识,例如将问题分解为子问题并存储这些子问题的......