首页 > 其他分享 >【DP】Leetcode 322 Coin Change

【DP】Leetcode 322 Coin Change

时间:2023-11-18 10:33:42浏览次数:41  
标签:硬币 int coins 322 amount Change Coin dp

题目链接

322. 零钱兑换

思路

因为硬币数量是无限的,所以无法以硬币数量作为状态进行遍历

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        if(n == 0){
            return -1;
        }

        // dp[i] 表示目标金额为 i 的情况下,所使用的最小硬币数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i){
            for(int j = 0; j < n; ++j){
                if(i - coins[j] >= 0){
                    // dp[i]有两种实现的方式,
                    // 一种是包含当前的coins[j],那么剩余钱就是 i-coins[j],这种操作要兑换的硬币数是 dp[i-coins[j]] + 1
                    // 另一种就是不包含,要兑换的硬币数是dp[i]
                    dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

标签:硬币,int,coins,322,amount,Change,Coin,dp
From: https://www.cnblogs.com/shixuanliu/p/17840157.html

相关文章

  • 小米日历配置exchange服务
    邮箱和日历账户的配置都要从邮件处进行配置首先在邮件的设置中添加邮箱,在此处配置pop3、imap、smtp和exchange服务需要注意的是foxmail和qq邮箱只是pop3、imap和smtp采用的服务器相同(但端口不同,此点存疑),但是exchange服务采用的服务器并不相同(这一点是通过原有设置发现的,以前添......
  • JavaScript: Checkbox onChange event is differently processed by IE and FF
     DropDownList onchange=""TextBoxonchange=""CheckBoxonclick=""RadioButtononclick="" JavaScript:CheckboxonChangeeventisdifferentlyprocessedbyIEandFFTrytoclick thefollowingbuttonsonIEandFirefox.U......
  • Hash模式基于锚点,以及onhashchange事件 —— 通过锚点的值作为路由地址
    前端路由有两种模式:mode:hash/histroyhash:1.hash的优点是兼容性比较高,可以直接在项目布署上线时使用。2.hash的缺点是#不美观影响url的美感,并且如果移动端分享严格限制,可能会报错history:1.history的优点是不会影响到url的美感,提高了可观赏性2.history的缺点是需要与后端搭配,......
  • error TS2322 Type 'string null' is not assignable to type 'string unXdefined'.
    这个错误消息涉及到Angular编译时的类型检查,特别是在Ivy编译器的部分编译模式下。错误消息本身提供了关键信息,但让我们详细解释这个错误的含义、可能的原因和如何修复它。错误消息:CompilingwithAngularsourcesinIvypartialcompilationmode.projects/storefrontlib/sha......
  • Git push到gerrit时报错change xxx closed
    Gitpush到gerrit时报错changexxxclosed报错日志:Tossh://xxxx![remoterejected]HEAD->refs/for/master(changehttp://xxxxm/+/96107closed)可以看到这个提交已经closed了,而change-Id未更改。即使用了已经合入的change-Id,在一次push的时候远端判断此change-Id......
  • CF911G Mass Change Queries
    题目描述:给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列.数据范围:\(1\len\le2\times10^5\)\(1\lea_i\le100\)\(1\leq\le2\times10^5,1\lel,r\len,1\lex,y\le100\)思路:观察数据范围,我们发现值域只有可怜的\(100\)所以一......
  • #2023-2024-1 20232322 《#2023-2024-1 20232322 《网络》第一周学习总结
    教材学习内容总结教材学习中的问题和解决过程-问题1:为何针对网络空间的攻击难以防范-问题1解决方案:一.攻击手段复杂多样:网络攻击者利用各种漏洞和恶意代码,以各种方式进行攻击,包括病毒、蠕虫、木马、勒索软件、拒绝服务攻击等。二.威胁来源难以确定:网络攻击往往来自于未知的I......
  • # 2023-2024-1 20231322 《计算机基础与程序设计》第七周学习总结
    |2022-2023-1-计算机基础与程序设计)||--|--||2022-2023-1计算机基础与程序设计第七周作业)||这个作业的目标|总结本周学习成果及疑问||作业正文|(https://www.cnblogs.com/cjl03/p/17827451.html)|教材学习内容总结数据结构:栈,队列,列表及其性质(线性);图,二叉数及其搜索;子程序教......
  • CF1322E - Median Mountain Range - 总结
    CF1322E-MedianMountainRange考虑分别对每个位置求出最后的数字。先枚举出这个数\(x\),并将\(a_i\gex\)的数设为\(1\),\(a_i<x\)的数设为\(0\),然后做题目中的操作,若为\(0\),则最终结果小于\(x\),为\(1\)则大于等于\(x\)。使用二分可以优化到\(\Omicron(n^2\log......
  • AtCoder Beginner Contest(abc) 322
    B-PrefixandSuffix难度:⭐题目大意给定两个字符串t和s,如果t是s的前缀则输出1,如果是后缀则输出2,如果都是则输出0,都不是则输出3;解题思路暴力即可;神秘代码#include<bits/stdc++.h>#defineintl1ngl1ng#defineIOSios::sync_with_stdio(false),cin.......