LeetCode.377 Combination Sum IV

字数统计: 246阅读时长: 1 min

 2019/08/15   Share

https://leetcode.com/problems/combination-sum-iv/

题意

给一个数组，求结果为target的组合数，数字可重复
解法

DFS，直接算会TLE，缓存中间结果后可以通过

class Solution {
 HashMap<Integer, Integer> cache = new HashMap<>();
 public int combinationSum4(int[] nums, int target) {
     if (target == 0) {
         return 1;
     } else if (target < 0) {
         return 0;
     }
     if (cache.containsKey(target)) {
         return cache.get(target);
     }
     int result = 0;
     for (int i = 0; i < nums.length; i++) {
         result += combinationSum4(nums, target - nums[i]);
     }
     cache.put(target, result);
     return result;
 }
}

动态规划

问题可以转换为求[1, target]之间每个位置有多少种排列方式, 这样将问题分化为子问题. 状态转移方程可以得到为:

dp[i] = sum(dp[i - nums[j]]), (i-nums[j] > 0);

边界值为dp[0] = 1，即target为0时有一种情况，即一个数也不选

class Solution {
  public int combinationSum4(int[] nums, int target) {
      int[] dp=new int[target+1];
      dp[0]=1;
      for(int i=1;i<=target;i++)
      {
          for(int j=0;j<nums.length;j++)
          {
              if(i>=nums[j])
                  dp[i]=dp[i]+dp[i-nums[j]];
          }
      }
      return dp[target];
  }
}

原文作者：Matteo

原文链接：http://tlzxsun.github.io/2019/08/15/LeetCode-377-Combination-Sum-IV/

发表日期：August 15th 2019, 7:11:35 pm

更新日期：August 15th 2019, 7:11:35 pm