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