LeetCode #494:Target Sum(目标和)

题目描述

乍一看本题和背包问题没关系,但也能转换成 01 背包问题进行求解。另外,不同于 #416 运用 01 背包求最多能装多少东西,本题是运用 01 背包解决排列组合问题,其递推公式略有不同。

按照题意,我们设 nums 数组中,所有添加正号的数和为 positiveSum、所有添加负号的数和为 negativeSum,显然有:

positiveSum - negativeSum = target
positiveSum + negativeSum = sum // sum为数组nums中所有数之和

上述两式中,我们消去 negativeSum,可得 positiveSum = (sum + target) / 2。由于 sum 和 target 对于一组数据来说是固定量,于是原问题就转化为:在数组 nums 中取若干个数,使得它们的和等于 positiveSum,有多少种不同取法(即装满容量为 positiveSum 的背包有多少种装法)?

之前都是求容量为 j 的背包,最多能装多少东西;而本题则是装满有几种方法,这就变成了 “组合” 问题。其递推公式为:

dp[j] = dp[j] + dp[j - nums[i]] // 不装物品i的情况加上装物品i的情况

完整代码实现如下。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0; i < n; i ++)
            sum += nums[i];
        
        if((target + sum) % 2 == 1) // 当target+sum为奇数时,无解,例如target=3、sum=4
            return 0;
        
        if(abs(target) > sum) // 当目标值的绝对值比sum还大,肯定无解
            return 0;
        
        int v = (target + sum) / 2;
        vector<int> dp(v + 1, 0);
        dp[0] = 1; // dp数组第0项初始化1,代表装满容量为0的背包只有一种方法(不装任何东西)
        for(int i = 0; i < n; i ++) {
            for(int j = v; j >= nums[i]; j --) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }

        return dp[v];
    }
};

发表回复

您的电子邮箱地址不会被公开。