【LeetCode】377. Combination Sum IV

淡淡的烟草味﹌ 2022-05-21 07:44 116阅读 0赞

> Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
> 
> 题解：通过数组中的元素进行组合，满足和等于target。每个元素可以重复利用。

*  解法一：动态规划（自下而上）：

> 该题跟上台阶有点类似，我们需要维护一个dp数组，dp\[i\]代表和为i在nums中得到的结果数，对每个i我们需要遍历数组nums，`当i >= num[x] 时，dp[i]+=dp[i-x]`.

--------------------

以nums=\[1,2,3\] target =4 为例：

3 = 1+x => x = 2  
3 = 2+x => x = 1  
3 = 3+x => x = 0  
即 dp\[3\] = dp\[2\]+dp\[1\]+dp\[0\]

--------------------

*  代码

public static int method(int[] nums,int target){
            int[] dp = new int[target+1];
            dp[0] = 1;
            for(int i = 1;i<=target ; i++){
                for(int num:nums){
                    if(i >=num) dp[i] +=dp[i-num];
                }
            }
            return dp[target];
    }

--------------------

*  解法二：使用递归加map（自上而下）：  
    
    
    > 该方法是使用map加上递归的方式解决，利用Map保存每个target的结果集。  
    > 遍历nums，  
    > 当target`<`nums\[i\]时，target=target-nums\[i\];将更新后的target以及target对应的解集存入map。

--------------------

*  代码

static Map<Integer,Integer> map = new HashMap<>();
        public static int combinationSum4(int[] nums, int target) {
            int count = 0;
            if(nums == null || nums.length == 0 || target < 0) return 0;
            if(target == 0) return 1;
            if(map.containsKey(target)) return map.get(target);
            for(int num : nums){
                count += combinationSum4(nums,target-num);
            }
            map.put(target,count);
            return count;
        }