LC322. 零钱兑换

这篇具有很好参考价值的文章主要介绍了LC322. 零钱兑换。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 代码随想录文章来源地址https://www.toymoban.com/news/detail-813737.html

class Solution {
    public int coinChange(int[] coins, int amount) {

        int max = Integer.MAX_VALUE;
        int [] dp = new int[amount+1];

        for(int j = 0 ; j < dp.length; j ++){
            dp[j] = max;
        }


        dp[0] = 0;

        for(int i = 0 ; i < coins.length; i ++){
            
            for(int j = coins[i] ; j <= amount ; 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] ;
    }
}

到了这里,关于LC322. 零钱兑换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(61)
  • LC322. 零钱兑换

     代码随想录

    2024年01月22日
    浏览(48)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(43)
  • leetcode 动态规划(爬楼梯、零钱兑换、完全平方数)

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月17日
    浏览(42)
  • 9.14零钱兑换(LC322-M)

    题目中说每种硬币的数量是无限的,可以看出是典型的完全背包问题。 1.确定dp及其下标: dp[j]:凑足总额为j所需钱币的最少个数为dp[j] 2.确定递推公式: 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])

    2024年03月12日
    浏览(44)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(47)
  • LeetCode518. 零钱兑换 II 以及 动态规划相关的排列组合问题

    一、题目 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 示

    2024年02月09日
    浏览(42)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II--求组合、组合总和IV--求排列)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(42)
  • 算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II)

    494. 目标和 - 力扣(LeetCode) 描述 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “

    2024年04月14日
    浏览(57)
  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

    # 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。

    2024年02月09日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包