给定一个整数数组 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]; } }