377.组合总和 Ⅳ

组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：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)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

1. dp数组的定义及下标的含义

dp[i][j] : 表示前i个数组成背包j的组合数为dp[i][j]

2. 状态转移方程

j<nums[i] , dp[i][j] = dp[i-1][j]

j≥nums[i], dp[i][j] = dp[i][j-nums[i]]+ dp[i][j-nums[i-1]]+…+ dp[i][j-nums[0]]

关于理解 j≥nums[i]时dp[i][j]的状态方程

因为这个是不分顺序并且是无穷背包 所以 前面的每个物品都有可能被装入背包

然后累加起来就是不分顺序的组合数

3. 初始化

初始第一行和第一列

第一列为1，因为背包为0时的组合数只有一个不取数即可。

package 力扣;

/** * @author yyq * @create 2022-06-21 18:18 */
public class leetcode377 {
    
    public static void main(String[] args) {
    
        leetcode377 leetcode377=new leetcode377();
        leetcode377.combinationSum4(new int[]{
    1,2,3},4);
    }
    public int combinationSum4(int[] nums, int target) {
    

        // 创建dp数组
        int[][] dp=new int[nums.length][target+1];

        // 初始化dp数组
        for (int i=0;i<nums.length;i++){
    
            dp[i][0] = 1;
        }
        for (int j=1;j<target+1;j++){
    
            if(j>=nums[0]){
    
                if(j%nums[0]==0){
    
                    dp[0][j] = 1;
                }
                else dp[0][j] = 0;
            }else dp[0][j] = 0;
        }
        // 填补dp数组
        // 外层循环物品 内层背包
        for (int i=1;i<nums.length;i++){
    
            for (int j=1;j<target+1;j++){
    
                if(j>=nums[i]){
    
                    for (int x=0;x<=i;x++){
    
                        dp[i][j] =dp[i][j] +  dp[i][j-nums[x]];
                    }
                }
                else dp[i][j] = dp[i-1][j];
            }
        }
        tools.printDP(dp,nums.length,target+1);
        return dp[nums.length-1][target];

    }
}