组合总和IV
https://leetcode.cn/problems/combination-sum-iv/description/
动态规划（二维数组）
在本题中，顺序不同的序列被视作不同的组合。若没有该要求，则为普通的组合问题，就可以采用完全背包的思路进行求解，此时示例1的所有组合为(1, 1, 1, 1)、(1, 1, 2)、(1, 3)、(2, 2)，输出结果应为4。本题实则为排列问题，不能直接使用完全背包的思路进行求解。
第一步：确定DP数组及下标含义
dp[i][j]定义为：在组合长度为i时，其元素之和为j的组合个数
题目指出nums中的各个元素都是正整数，因此在极端情况下target可由target个1相加得到，因此dp数组的行数设定为target+1
输出结果即为dp数组最后一列之和：dp[0][target] (组合长度为1时，其元素之和为target的组合个数) + dp[1][target] (组合长度为1时，其元素之和为target的组合个数) + …… + dp[target][target] (组合长度为target时，其元素之和为target的组合个数)
1
2
3
4
5
6
7
8
9
10
|
j →
i↓ 0 1 2 3 4
---------------------
0 [? ? ? ? ?]
1 [? ? ? ? ?]
2 [? ? ? ? ?]
3 [? ? ? ? ?]
4 [? ? ? ? ?]
↓
return dp[0][4] + …… + dp[1][4]
|
第二步：确定递推公式
dp[i][j]为长度为i时的组合，是由长度为i+1的组合在末尾添加一个数字构成，而末尾添加的数字可以是nums数组中的任何一个。当末尾添加的数字选择nums[0]的时候，对于长度为i+1的组合，需要其元素之和为j-nums[0]，满足这样的组合个数为dp[i-1][j-nums[0]]。对于末尾选择其他数字，同理可得。因此其转移方程为：
$$
dp[i][j] = \sum_{i=1}^{nuns.length} dp[i-1][j-nums[k]], j-nums[k] \geq0
$$
1
2
3
4
5
6
7
8
9
10
|
j →
i↓ 0 1 2 3 4
---------------------
0 [1 0 0 0 0]
1 [? ? ? ? ?]
↓ nums = {1,2,3}
dp[1][2] = dp[0][2-1] + dp[0][2-2] = 0 + 1 = 1
2 [? ? ? ? ?]
3 [? ? ? ? ?]
4 [? ? ? ? ?]
|
第三部：DP数组的初始化
当组合的长度为0时，各元素之和只能为0，因此要想让和为0有且只有这一个方案，即dp[0][0]=1，第一行的其他元素全部为0
1
2
3
4
5
6
7
8
|
j →
i↓ 0 1 2 3 4
---------------------
0 [1 0 0 0 0]
1 [? ? ? ? ?]
2 [? ? ? ? ?]
3 [? ? ? ? ?]
4 [? ? ? ? ?]
|
第四步：确定遍历顺序
转移方程表明当前行取决于上一行，因此外层循环为遍历i、内层循环遍历j
第五步：举例推导
1
2
3
4
5
6
7
8
9
10
|
j →
i↓ 0 1 2 3 4
---------------------
0 [1 0 0 0 0]
1 [0 1 1 1 0]
2 [0 0 1 2 3] → (1, 3) (2, 2) (3, 1)
3 [0 0 0 1 3] → (1, 1, 2) (1, 2, 1) (2, 1, 1)
4 [0 0 0 0 1] → (1, 1, 1, 1)
↓
7
|
Java代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class combinationSum4 {
static class Solution {
public int combinationSum4(int[] nums, int target) {
// i为组合的长度 组合的最大长度为target
// j为组合中各元素之和的目标值
int[][] dp = new int[target + 1][target + 1];
// 组合长度为0时的元素之和为0
dp[0][0] = 1;
// 输出结果为最后一列值之和
int res = 0;
for (int i = 1; i <= target; i++) {
for (int j = 0; j <= target; j++) {
for (int k = 0; k < nums.length; k++) {
// 状态转移方程
if (j - nums[k] >= 0) {
dp[i][j] = dp[i][j] + dp[i - 1][j - nums[k]];
}
}
}
// 累加最终的输出结果
res = res + dp[i][target];
}
return res;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.combinationSum4(new int[]{1, 2, 3}, 4));
}
}
|