首页 > 编程语言 >算法学习day44动态规划part06-518、377

算法学习day44动态规划part06-518、377

时间:2023-06-05 23:57:51浏览次数:56  
标签:target nums int coins part06 518 day44 public dp

package LeetCode.DPpart06;
/**
 * 518. 零钱兑换 II
 * 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
 * 假设每一种面额的硬币有无限个。
 * 题目数据保证结果符合 32 位带符号整数。
 * 示例:
 * 输入:amount = 5, coins = [1, 2, 5]
 * 输出:4
 * 解释:有四种方式可以凑成总金额:
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * */

public class CoinChangeII_518 {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];
        // 只有一种硬币的情况
        for (int i = 0; i <= amount; i += coins[0]) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                // 第i种硬币使用0~k次,求和
                for (int k = 0; k * coins[i] <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
                }
            }
        }
        return dp[coins.length - 1][amount];
    }
}
package LeetCode.DPpart06;
/**
 * 377. 组合总和 Ⅳ
 * 给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 * 题目数据保证答案符合 32 位整数范围。
 * 示例:
 * 输入:nums = [1,2,3], target = 4
 * 输出:7
 * 解释:
 * 所有可能的组合为:
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意,顺序不同的序列被视作不同的组合。
 * */

public class CombinationSumIV_377 {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

}

 

标签:target,nums,int,coins,part06,518,day44,public,dp
From: https://www.cnblogs.com/lipinbigdata/p/17459325.html

相关文章

  • 算法学习day37贪心part06-738、968
    packageLeetCode.greedypart06;/***738.单调递增的数字*当且仅当每个相邻位数上的数字x和y满足x<=y时,我们称这个整数是单调递增的。*给定一个整数n,返回小于或等于n的最大数字,且数字呈单调递增。*示例:*输入:n=332*输出:299**/public......
  • 算法学习day30回溯part06-332、51、37
    packageLeetCode.backtrackpart06;importjava.util.ArrayList;importjava.util.Collections;importjava.util.LinkedList;importjava.util.List;/***332.重新安排行程*给你一份航线列表tickets,其中tickets[i]=[fromi,toi]表示飞机出发和降落的机场地点......
  • 518.零钱兑换II
    给你一个整数数组coins表示不同面额的硬币,另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回0。假设每一种面额的硬币有无限个。题目数据保证结果符合32位带符号整数。输入:amount=5,coins=[1,2,......
  • hdu 5188(限制01背包)
    zhxandcontestTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionAsoneofthemostpowerfulbrushesintheworld,zhxusuallytakespartinallkindsofcontests.Oneday,zhxtakespar......
  • [20230518]建立索引导致的性能问题3.txt
    [20230518]建立索引导致的性能问题3.txt--//生产系统遭遇建立索引导致的性能问题,建立的sqlprofile里面包含索引名提示,很少见,改索引名导致sqlprofile失效,--//当然我遇到的情况有一点点不同,建立新索引,然后旧索引设置不可见(相当于改名),今天测试看看修改sqlprofile的内容是......
  • SSO2.0 8-20230518
             ......
  • 总结20230518
    代码时间(包括上课)1h代码量(行):30行博客数量(篇):1篇相关事项:1、今天上午没课,把形势与政策写了,但是查重不过关,今天晚上在完善完善。2、今天下午上的是体育,进行了体育考试,结果非常的不理想,步法不知道怎么个事,跑的也太慢了。......
  • day44| 518+377
    518.零钱兑换II 题目简述:给你一个整数数组coins表示不同面额的硬币,另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回0。假设每一种面额的硬币有无限个。 题目数据保证结果符合32位带符号整数。......
  • HarmonyOS Hi3518系列 环境篇①——HiSpark_IPC_DIY摄像头开箱组装
    文章目录一、硬件介绍二、组装一、硬件介绍本专栏的所有开发都基于硬件润和HiSpark_IPC_DIY摄像头(Hi3518E)开发板套件,二、组装按照说明书进行组装,挺简单的,不过中间也装反过一次。组装后的成品多角度拍了几张照片,如有正在组装的同学看到可以多对照着看。......
  • day44 377. 组合总和 Ⅳ |
    给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。示例:nums=[1,2,3]target=4所有可能的组合为:(1,1,1,1)(1,1,2)(1,2,1)(1,3)(2,1,1)(2,2)(3,1)请注意,顺序不同的序列被视作不同的组合。 classSolution{......