给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。
数据范围:数组长度满足
,数组中的数和 target 大小满足 
private int recurrent(int[] nums, int depth, int rest, int[][] mem) { if(rest < 0){ return 0; } if(rest == 0){ return 1; } if(mem[depth][rest] > 0) return mem[depth][rest]; for(int i = depth; i < nums.length; i++){ mem[depth][rest] += recurrent(nums, i, rest - nums[i], mem); } return mem[depth][rest]; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param target int整型 * @param nums int整型一维数组 * @return int整型 */ public int change (int target, int[] nums) { // write code here int n = nums.length; int[][] dp = new int[n][target + 1]; for(int i = 0; i < n; i++){ dp[i][0] = 1; } for(int i = n - 1; i >= 0; i--){ for(int j = nums[i]; j <= target; j++){ dp[i][j] = (i < n - 1? dp[i + 1][j]: 0) + dp[i][j - nums[i]]; } } return dp[0][target]; } }最后我们注意到,dp[i][j]只依赖其下一行及左边的值,因此还可以进行空间压缩,dp用一维数组就可以,这也就是我们经常看到的背包问题解法。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param target int整型 * @param nums int整型一维数组 * @return int整型 */ public int change (int target, int[] nums) { // write code here int n = nums.length; int[] dp = new int[target + 1]; dp[0] = 1; for(int i = n - 1; i >= 0; i--){ for(int j = nums[i]; j <= target; j++){ dp[j] += dp[j - nums[i]]; } } return dp[target]; } }
public static int change(int target, int[] nums) { // write code here // dp[i] 表示凑出金额 i 的组合数 int[] dp = new int[target + 1]; dp[0] = 1;// 什么都不取,直接凑成0,因此为1,这是后续的启动 for (int i = 1; i <= target; i++) { // 选择每种金额的前提下,找到凑出 i 的可能数,并相加 for (int money : nums) { // 只有金额比当前i小,才可能凑出来 if (money <= i) { dp[i] += dp[i - money]; } } } return dp[target]; }解释:对于外层遍历 target, 内层遍历 nums 的解法,咋一看是没问题,但仔细想想会发现这种解法考虑所有的排列组合形式,当我们求解 dp[i] 的时候,在当前元素为 money 的情况下,i (i >= money, 否则无法凑成i),我们知道 money 可以与 dp[i - money] 的所有组合构成 dp[i], 但我们是首先择了 money 作为前提,如果后续遍历到 second, second 与 money 组合也能凑成 i ,则组成i 的方式有了 [money, second] 和 [second, money], 很明显这是重复了,因此结果会偏大,只是举了最简单的例子说明了一下问题
public static int change(int target, int[] nums) { int[] dp = new int[target + 1]; dp[0] = 1;// 什么都不取,直接凑成0,因此为1,这是后续的启动 for (int money : nums) { for (int i = 1; i <= target; i++) { // 对于每个money 更新每个 target // 如果 i 比 money还小,选择 money 的前提下,无法凑成 目标值 if (i - money >= 0) dp[i] += dp[i - money]; } } return dp[target]; }
class Solution: def change(self, target: int, nums: List[int]) -> int: dp = [0] * (target + 1) dp[0] = 1 for num in nums: for i in range(num, target + 1): dp[i] += dp[i - num] return dp[target]
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param target int整型 * @param nums int整型一维数组 * @return int整型 */ function change(target, nums) { const dp = new Array(target + 1).fill(0); dp[0] = 1; for (const num of nums) { for (let i = num; i <= target; i++) { dp[i] += dp[i - num]; } } return dp[target]; } module.exports = { change: change };
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param target int整型 * @param nums int整型vector * @return int整型 */ int change(int target, vector<int>& nums) { // write code here vector<int> dp(target+1, 0); dp[0]=1; for(int i=0;i<nums.size();i++) { for(int j=nums[i];j<=target;j++) { dp[j]+=dp[j-nums[i]]; } } return dp[target]; } };
import java.util.*; public class Solution { public int change (int target, int[] nums) { int n = nums.length; int[][] dp = new int[n+1][target+1]; for(int i=0; i<=n; i++) dp[i][0] = 1; for(int i=1; i<=n; i++){ for(int j=1; j<=target; j++){ if(j - nums[i-1] >= 0) dp[i][j] = dp[i-1][j] + dp[i][j-nums[i-1]]; else dp[i][j] = dp[i-1][j]; } } return dp[n][target]; } }