Leetcode: Combination Sum IV && Summary: The Key to Solve DP
2023-09-11 14:14:07 时间
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. Example: nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7. Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
DP 解法: the key to solve DP problem is to think about how to create overlap, how to re-solve subproblems(怎么制造复用)
Bottom up dp:
1 public class Solution { 2 public int combinationSum4(int[] nums, int target) { 3 if (nums==null || nums.length==0) return 0; 4 Arrays.sort(nums); 5 int[] dp = new int[target+1]; 6 dp[0] = 1; 7 for (int i=1; i<=target; i++) { 8 for (int j=0; j<nums.length && nums[j]<=i; j++) { 9 dp[i] += dp[i-nums[j]]; 10 } 11 } 12 return dp[target]; 13 } 14 }
Better Solution(Bottom-up)不sort也成:
1 public int combinationSum4(int[] nums, int target) { 2 int[] comb = new int[target + 1]; 3 comb[0] = 1; 4 for (int i = 1; i < comb.length; i++) { 5 for (int j = 0; j < nums.length; j++) { 6 if (i - nums[j] >= 0) { 7 comb[i] += comb[i - nums[j]]; 8 } 9 } 10 } 11 return comb[target]; 12 }
Follow up:
I think if there are negative numbers in the array, we must add a requirement that each number is only used one time, or either positive number or negative number should be used only one time, otherwise there would be infinite possible combinations.
For example, we are given:
{1, -1}, target = 1,
it's obvious to see as long as we choose n 1s and (n-1) -1s, it always sums up to 1, n can be any value >= 1.
相关文章
- Couldn't get connection because we are at maximum connection count (150/150) and there are none 异常解决
- [UI] Elastic Stack & scrollReveal.js
- 【栈&队列】LeetCode 394. 字符串编码【中等】
- 【队列&栈】LeetCode 84. 柱状图中最大的矩形【困难】
- 【数组&双指针】leetcode 283. 移动零【简单】
- [AWS DA] AWS Monitoring & Audit: CloudWatch, X-Ray and CloudTrail
- [AngularJS + Webpack] Requiring CSS & Preprocessors
- 【数组&双指针】LeetCode 1. 两数之和【简单】
- 【数组&双指针】LeetCode 142. 环形链表 II【中等】
- 【数组&双指针】LeetCode 76. 最小覆盖子串【困难】
- 红与黑(bfs&dfs)
- Interop type 'Microsoft.Office.Interop.Word.ApplicationClass' cannot be embedded. Use the applicable
- 【大数据&AI人工智能】机器意识能走多远:未来的人工智能哲学
- 【大数据&AI人工智能】每个现代数据科学家都必须阅读的 6 篇论文| 6 Papers Every Modern Data Scientist Must Read
- HDU 1159 && POJ 1458
- leetcode笔记:Pascal's Triangle
- [leetcode]Pascal's Triangle II