377.组合总和--从两种角度出发的思考

发表于 Artalk： loading...
完全背包 动态规划

题目来自leetcode 377. 组合总和 Ⅳ，属于完全背包问题的“变种”。本文从不同角度出发进行了分析

题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例

1
2
3
4
5
6
7
8
9
10
11
12
输入：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)
请注意，顺序不同的序列被视作不同的组合。

分析

首先，本题求的是排列，例如，(1,3) 和 (3,1) 视作不同的结果

如果从完全背包的角度出发

降低维度优化空间占用后，转移方程 dp[j]=dp[j]+dp[j−nums[i]]dp[j] = dp[j] + dp[j - nums[i]]

计算状态时，可以先遍历数字（物品）再遍历加和（背包容量），也可以先遍历背包容量，后遍历物品

1
2
3
4
5
for (int j = 0; j <= amount; j++) { // 遍历背包容量
 for (int i = 0; i < nums.size(); i++) { // 遍历物品
     if (j - nums[i] >= 0) dp[j] += dp[j - nums[i]];
 }
}

因为，在完全背包问题中，即便是先遍历背包容量后遍历物品，当前状态 dp[j]dp[j] 也可以正确地从上一个状态 dp[j−nums[i]]dp[j-nums[i]] （「左上」）转移过来

1
2
3
4
5
6
7
————————————>背包容量
| 1  6 
| 2  7
| 3  8
| 4  9
v 5  ...
物品

@muluo的题解

如果先遍历背包容量,再遍历物品的话，那么对于每一个容量，都会经历 1 和 3 的计算，结果中会包含 (1, 3) 和 (3, 1) 两种结果，符合求「排列」的要求

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 完全背包问题
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int cur = 1; cur <= target; ++cur) {
            for (int u : nums) {
                if (cur >= u) dp[cur] += dp[cur - u];
            }
        }
        return dp[target];
    }
}

从普通动态规划的角度去做

受到之前计数DP-整数划分中Y总的思路启发，我们可以从方案中元素的个数入手

定义 dp[i][j]dp[i][j] 表示组合的加和为 ii 且组合长度为 jj 的方案个数

转移方程 dp[i][j]=∑k∈[0,n)dp[i−nums[k]][j−1]dp[i][j] = \sum_{k \isin[0,n)} dp[i - nums[k]][j - 1]

即组合长度为 jj 的状态可以由 jj-11 转移而来，当前组合的第 jj 个数字（物品），可以选取任意一个数字（背包中任意一个物品）

最终结果，应该是对所有长度的结果集求和 ans=∑j∈[1,len]dp[target][j]ans=\sum_{j\isin [1,len]}dp[\text{target}][j] ，其中 len = target

正整数最小为 1，因此结果集的最大长度情况，为 target 个 1，最大长度为 target

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int ans = 0, len = target;
        int[][] dp = new int[target + 1][len + 1];
        dp[0][0] = 1;
        for (int i = 0; i <= target; ++i) {
            for (int j = 1; j <= len; ++j) {
                for (int u : nums) {
                    if (i >= u) dp[i][j] += dp[i - u][j - 1];
                }
            }
        }
        for (int j = 1; j <= len; ++j) ans += dp[target][j];
        return ans;
    }
}

那么问题来了，可以不可以对空间占用进行优化？

由于状态总是从 j−1→jj-1\to j 进行转移，不依赖其他状态，那么可以省去组合长度这个维度（就跟背包问题省去「物品」维度一个道理）

重新定义一个一维的状态数组 dp[i]dp[i] ，表示加和（背包容量）为 ii 的方案数

计算状态的转移时，可以直接忽略方案的长度这一维度。因为 dp[i]dp[i] 进行转移时，每一个数字（物品）都可以被无限选取，选一个，方案的长度就会加一，无需特地针对方案长度进行循环，最终计算出来的 dp[target]dp[target] 中就包含了各种长度的方案

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
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 u : nums) {
                if (i >= u) dp[i] += dp[i - u];
            }
        }
        return dp[target];
    }
}

观察一下就会发现，代码形式上，跟从完全背包角度出发的一模一样！