dp背包解决组合问题——494. 目标和

我们可以在所有数字前都加上+或-，这里我们将前面为-的数字进行求和，将n个+和m个-的情况转换成（m+n-1）个+和1个-的情况

这样我们就可以把问题转换为，把整个数组分为两组，使得两组的差为target，问：有几种分组的方法？

我们假设两组的和分别为a1、a2，数组的总和为sum，这样有a1+a2=sum，a1-a2=target（假设a1>a2），如果我们用01背包的方法解，问题就是：容量为a1的背包被装满，有多少种方法

这就和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少，而这次是问装满有多少种方法

dp[i][j] 表示：当前有0…i号物品，填满$j$这么大容量的背包，有dp[i][j]种方法

求组合类问题的公式，都是类似这种：

dp[i][j] = dp[i-1][j - nums[i]] + dp[i-1][j]
1

对于0…i号物品，容量为j的背包装满的方法数dp[i][j]，等于装物品nums[i]且装满的方法数dp[i-1][j-nums[i] + 不装物品nums[i]且装满的方法数dp[i-1][j]

初始化第0行时，计算当前位置需要使用前面位置的数，为避免覆盖，需要从后往前遍历

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((sum + target) % 2 != 0 || abs(target) > sum) {
            // 奇数
            return 0;
        }
        int n = nums.size();
        int content = (sum + target) / 2;
        if (content < 0) {
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(content + 1, 0));
		
		// 0号物品装满容量为0的背包，只有1种方法，那就是不装
        dp[0][0] = 1;
        // 由于计算当前位置需要使用前面位置的数，必须从后往前遍历
        for(int j = content; j >= nums[0]; j--){
            dp[0][j] = dp[0][j - nums[0]] + dp[0][j];   // 装nums[i]装满，不装nums[i]装满
        }

        for (int i = 1; i < n; i++) {
            // 由于使用上一行的结果计算当前行，不存在覆盖的问题，正序逆序皆可
            for (int j = 0; j <= content; j++) {
                if (j < nums[i]) {
                	// 当前容量j小于当前物品nums[i]，无法装入nums[i]，则用前i-1个物品装满容量j
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j]; // 装nums[i]装满，不装nums[i]装满
                }
            }
        }
        return dp[n - 1][content];
    }
};
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
32
33
34
35
36
37

根据上面二维dp数组改为一维滚动数组

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((sum + target) % 2 != 0 || abs(target) > sum) {
            // 奇数
            return 0;
        }
        int n = nums.size();
        int content = (sum + target) / 2;
        if (content < 0) {
            return 0;
        }
        vector<int> dp(content+1, 0);
		
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = content; j >= nums[i] ; j--) {
            	// 之所以不用像二维数组一样，需要判断当前容量j是否大于当前物品nums[i]
            	// 是因为二维dp数组中，若当前容量j小于当前物品nums[i]，则使用前i-1个物品装满容量j，即dp[i-1][j]
            	// 需要拷贝上一行的结果，在滚动数组中，不做操作，也就保留了“上一行”的结果
                dp[j] = dp[j - nums[i]] + dp[j]; // 装nums[i]装满，不装nums[i]装满
            }
        }
        return dp[content];
    }
};
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