力扣第494题目标和 c++ 动态规划 c++ 01背包难~~-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣第494题目标和 c++ 动态规划 c++ 01背包难~~。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

494. 目标和

中等

思路和解题方法

首先，代码计算了数组 nums 中所有元素的总和，并将结果保存在变量 sum 中。如果目标值 S 的绝对值大于 sum，说明无法通过改变符号使得数组元素的和等于 S，此时直接返回 0。如果 (S + sum) % 2 == 1，说明无法通过改变符号使得数组元素的和等于 S，此时直接返回 0。否则，计算背包容量 bagSize 为 (S + sum) / 2，表示需要选择一些数，使得它们的和等于 bagSize。

然后，创建一个大小为 bagSize+1 的动态规划数组 dp，并将所有元素初始化为 0。将 dp[0] 设为 1，表示当不选择任何数时，它们的和为 0，有一种方案。

接着，使用双重循环遍历数组 nums 和背包容量 bagSize。内层循环从 bagSize 开始向前遍历，每次考虑当前数是否放入背包中。如果当前数的值小于等于当前背包容量 j，则可以选择将其放入背包中，更新 dp[j] 的值为 dp[j] + dp[j - nums[i]]。这样，dp[j] 表示容量为 j 的背包所能装载的方案数。

最后，返回结果 dp[bagSize]，表示选择一些数，使得它们的和等于 bagSize 的方案数。

复杂度

时间复杂度:

O(n*m)

时间复杂度：O(n×m)，其中 n 表示数组 nums 的长度，m 表示背包的容量，即 (S + sum) / 2。在动态规划中，我们需要遍历数组 nums 和背包容量 m，因此总时间复杂度为 O(n×m)。

空间复杂度

O(m)

空间复杂度：O(m)，其中 m 表示背包的容量，即 (S + sum) / 2。我们需要一个大小为 m + 1 的动态规划数组来存储中间结果，因此空间复杂度为 O(m)。

c++ 代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        // 计算数组中所有元素的总和
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        
        // 如果目标值的绝对值大于数组元素总和，无法通过符号改变得到目标值，直接返回 0
        if (abs(S) > sum) return 0;
        
        // 如果目标值和数组元素总和的和为奇数，无法通过符号改变得到目标值，直接返回 0
        if ((S + sum) % 2 == 1) return 0;
        
        // 计算背包容量
        int bagSize = (S + sum) / 2;
        
        // 创建动态规划数组，并将所有元素初始化为 0
        vector<int> dp(bagSize + 1, 0);
        
        // 当不选择任何数时，它们的和为 0，有一种方案
        dp[0] = 1;
        
        // 使用双重循环遍历数组和背包容量
        for (int i = 0; i < nums.size(); i++) { // 遍历数组
            for (int j = bagSize; j >= nums[i]; j--) { // 遍历背包容量
                // 如果当前数的值小于等于当前背包容量，可以选择将其放入背包中
                // 更新 dp[j] 的值为 dp[j] + dp[j - nums[i]]，表示容量为 j 的背包所能装载的方案数
                dp[j] += dp[j - nums[i]];
            }
        }
        
        // 返回选择一些数，使得它们的和等于背包容量的方案数
        return dp[bagSize];
    }
};

具体解释部分

if (abs(S) > sum) return 0; // 此时没有方案

if ((S + sum) % 2 == 1) return 0; // 此时没有方案

第一个条件判断语句 if (abs(S) > sum) return 0; 的意思是，如果目标值 S 的绝对值大于数组 nums 中所有元素的总和 sum，那么无论如何改变符号，都无法使得数组元素的和等于目标值 S。因此，直接返回 0，表示此时没有任何方案可以满足要求。

第二个条件判断语句 if ((S + sum) % 2 == 1) return 0; 的意思是，如果目标值 S 和数组 nums 中所有元素的总和 sum 的和为奇数，那么无论如何改变符号，都无法使得数组元素的和等于目标值 S。因为奇数无法通过加减操作得到偶数。所以直接返回 0，表示此时没有任何方案可以满足要求。

   int bagSize = (S + sum) / 2;

bagSize 表示背包的容量。由于我们要寻找一些数，使得它们的和等于目标值 S，而且我们可以通过改变符号来实现，因此我们可以将问题转化为一个经典的 0-1 背包问题。

假设我们将所有正数的符号取为正号，将所有负数的符号取为负号，那么所有数的和就是 sum。我们的目标是找到一些数，使得它们的和等于目标值 S。

由于我们只能改变数的符号，因此我们可以将原问题转化为：从数组 nums 中选择一些数，使得它们的和等于 (S + sum) / 2。这里的 (S + sum) / 2 表示背包的容量，也就是我们要达到的目标和。