这四道题目相似，只是有不同的区别，这里记录一下这四道题目的DP解法。 leetcode39：Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1:
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] python代码如下：
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: cache = [[] for _ in range(target + 1)] cache[0] = [[]] for c in candidates: for i in range(target + 1): if i >= c: for temp_ans in cache[i - c]: cache[i].append(temp_ans + [c]) return cache[-1]leetcode40：Combination Sum II Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ] 代码如下：
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() dp = [set() for i in range(target+1)] dp[0].add(()) for num in candidates: for t in range(target, num-1, -1): for prev in dp[t-num]: dp[t].add(prev + (num,)) return list(dp[-1])leetcode216 Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Note:
All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1:
Input: k = 3, n = 7 Output: [[1,2,4]] Example 2:
Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]
def combinationSum3(self, k: int, n: int) -> List[List[int]]: dp = [[] for _ in range(n + 1)] for i in range(1, 10): for j in range(n, i - 1, -1): if j == i: dp[j] += [[i]] else: if dp[j - i]: dp[j] += [[i] + arr for arr in dp[j - i]] return list(filter(lambda arr : len(arr) == k, dp[-1]))leecode377 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. 代码如下：
def combinationSum4(self, nums: List[int], target: int) -> int: dp=[0 for i in range(target+1)] dp[0]=1 for i in range(1,target+1): for num in nums: if num<=i: dp[i]+=dp[i-num] return dp[target]这几个题目很类似，递推式子都一样,但是由细微的差别，有意思的是这些差别可以通过改变迭代的顺序和方向来求出解决办法，很有意思哈哈
