Leetcode 494 目标和

1. 题目描述

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

示例 2：

2. 我的尝试

该问题可以转化为“0-1背包问题”。

记整个数组的元素和为sum，则对于给定target，我们只需要从数组中挑出若干元素添加 '-' 号。这些元素的和 m m m 应该等于 ( s u m − t a r g e t ) ÷ 2 (sum - target) \div 2 (sum−target)÷2 。这样，我们就把本题转化成了一个背包容量是 m m m 的 0-1背包问题。

当然，如果 s u m − t a r g e t sum - target sum−target 为奇数或者为负数，那么说明不存在满足题意的构造方式，直接返回0就可以了。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 物品数量
        int n = nums.size();

        // 数组内元素总和
        int sum_ = 0;
        for (auto &x : nums) sum_ += x;


        // 计算需要添加'-'号的元素的总和
        int m = (sum_ - target) / 2;

        // (sum_ - target)是奇数或者为负数，直接返回0
        if (m * 2 + target != sum_ || m < 0) return 0;

        // 状态数组的初始化
        int f[m + 1];
        for (int i = 0; i <= m; i++) f[i] = 0;
        f[0] = 1;

        // f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i]]
        // 其中 i 是迭代轮数，j 是背包容量

        for (int i = 0; i < n; i++)
            for (int j = m; j >= nums[i]; j--) 
                f[j] = f[j - nums[i]] + f[j];

        return f[m];
    }
};