「力扣」第 377 题:组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3] target = 4 所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意,顺序不同的序列被视作不同的组合。 因此输出为 7。
进阶:
如果给定的数组中含有负数会怎么样?
问题会产生什么变化?
我们需要在题目中添加什么限制来允许负数的出现?致谢:
特别感谢 @pbrother 添加此问题并创建所有测试用例。
方法:动态规划
题意分析:
- 输入数组的每个元素可以使用多次,这一点和「完全背包」问题有点像;
- 顺序不同的序列被视作不同的组合,这一点和所有的「背包问题」都不同。
思路分析:
- 遇到这一类问题,做一件事情有很多种做法,每一种做法有若干个步骤,脑子里能想到的常规思路大概有「回溯搜索」、「动态规划」;
- 由于不用得到具体的组合表示,因此考虑使用「动态规划」来解。
我们先画树形图分析。
很容易发现「重复问题」,因此,我们可以使用「动态规划」来做,如果题目问具体的解,那么用「回溯搜索」做(「力扣」第 39 题:组合之和)。
对上图的解释:
怎么写代码呢?
递归求解:由于有大量「重复子问题」,因此必须使用缓存,以避免相同问题重复求解,这个方法叫「记忆化搜索」,在《算法导论》这本书上也把它归入到「动态规划」的定义中。这种思考问题的方式是「从上到下」的,直接面对问题求解,遇到什么问题,就解决什么问题,同时记住结果;
「动态规划」告诉了我们另一种思考问题的方式:「从底向上」,可以不直接面对问题求解,从这个问题最小的样子开始,通过逐步递推,至到得到所求的问题的答案。
虽然这个问题没有明显的「最优子结构」,但这种「从底向上」递推的思路是很深刻的,我们也把它归纳到「动态规划」的解法中。
方法:动态规划
“动态规划”的两个步骤是思考“状态”以及“状态转移方程”。
1、状态
对于“状态”,我们首先思考能不能就用问题当中问的方式定义状态,上面递归树都画出来了。当然就用问题问的方式。
dp[i]
:对于给定的由正整数组成且不存在重复数字的数组,和为 i
的组合的个数。
思考输出什么?因为状态就是问题当中问的方式而定义的,因此输出就是最后一个状态 dp[n]
。
2、状态转移方程
由上面的树形图,可以很容易地写出状态转移方程:
dp[i] = sum{dp[i - num] for num in nums and if i >= num}
注意:在 $0$ 这一点,我们定义 dp[0] = 1
的,它表示如果 nums
里有一个数恰好等于 target
,它单独成为 $1$ 种可能。
参考代码:
Java 代码:
public class Solution {
/**
* 这里状态定义就是题目要求的,并不难,状态转移方程要动点脑子,也不难:
* 状态转移方程:dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + ... (当 [] 里面的数 >= 0)
* 特别注意:dp[0] = 1,表示,如果那个硬币的面值刚刚好等于需要凑出的价值,这个就成为 1 种组合方案
* 再举一个具体的例子:nums=[1, 3, 4], target=7;
* dp[7] = dp[6] + dp[4] + dp[3]
* 即:7 的组合数可以由三部分组成,1 和 dp[6],3 和 dp[4], 4 和dp[3];
*
* @param nums
* @param target
* @return
*/
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 这个值被其它状态参考,设置为 1 是合理的
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
Java 代码:
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < target; i++) {
for (int num : nums) {
if (i + num <= target) {
dp[i + num] += dp[i];
}
}
}
return dp[target];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
int target = 4;
int res = solution.combinationSum4(nums, target);
System.out.println(res);
}
}
Python 代码:
class Solution:
def combinationSum4(self, nums, target):
size = len(nums)
if size == 0 or target <= 0:
return 0
dp = [0 for _ in range(target + 1)]
# 这一步很关键,想想为什么 dp[0] 是 1
# 因为 0 表示空集,空集和它"前面"的元素凑成一种解法,所以是 1
# 这个值被其它状态参考,设置为 1 是合理的
dp[0] = 1
for i in range(1, target + 1):
for j in range(size):
if i >= nums[j]:
dp[i] += dp[i - nums[j]]
return dp[-1]