337.组合总和Ⅳ
给你一个由 不同 整数组成的数组 nums
,和一个目标整数 target
。请你从 nums
中找出并返回总和为 target
的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1:
输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:
输入:nums = [9], target = 3
输出:0
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums
中的所有元素 互不相同1 <= target <= 1000
题解:
本题相较于518.零钱兑换Ⅱ有很相似的地方,都是完全背包的应用场景,区别在于,518题是求解的组合数,而本题求解的是序列数。
具体的思路这里就不说了,可以去别的地方找详解,说一下我这个题踩到的坑(仅限菜鸡)。
由于滚动数组的逻辑写起来让我感觉混乱,因此我的写法还是喜欢停留在使用二维dp来求解。然后组合数和序列数这两种情况,虽然有点难以理解,但是记忆了对应的代码写法,无非是两个for循环的位置换一下。
- 组合数:先遍历物品,再遍历背包容量
- 序列数:先遍历背包容量,再遍历物品
因此我很快的写出了下面的代码(错的)
package com.offer;
import com.offer.leetcode.datastruct.DPUtils;
/**
* @author bwzfy
* @create 2024/4/14
**/
public class _377组合总和Ⅳ {
public static void main(String[] args) {
System.out.println(combinationSum4(new int[]{1, 2, 3},
4));
}
public static int combinationSum4(int[] nums, int target) {
int[][] dp = new int[nums.length + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i < nums.length + 1; i++) {
dp[i][0] = 1;
}
for (int j = 1; j < target + 1; j++) {
for (int i = 1; i < nums.length + 1; i++) {
if (nums[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
DPUtils.printDP(dp);
return dp[nums.length][target];
}
}
由于前面练习的背包题,因此这个题写的很流畅,运行测试用例的时候还是很自信的,结果没过。。。。
打印出来的dp如下:
思来想去没想明白,然后再使用518题的代码来运行了一下,打印出了二维数组,发现在使用二维数组的情况下,两个for循环的位置是不重要的,他们求的都是组合数(裂开)。
因此后来改了滚动数组的写法,得到了正确的结果,代码如下。
package com.offer;
import com.offer.leetcode.datastruct.DPUtils;
/**
* @author bwzfy
* @create 2024/4/14
**/
public class _377组合总和Ⅳ {
public static void main(String[] args) {
System.out.println(combinationSum4(new int[]{1, 2, 3},
4));
}
public static int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 1; j < target + 1; j++) {
for (int i = 1; i < nums.length + 1; i++) {
if (nums[i - 1] <= j) {
dp[j] = dp[j] + dp[j - nums[i - 1]];
}
}
}
DPUtils.printDP(dp);
return dp[target];
}
}
总结得到的结果就是,双重for循环的位置的意义仅对于滚动数组有效,以后再遇到这种完全背包的求个数问题,需要使用滚动数组来写。