494. 目标和

发表于 分类于 阅读次数： Waline： 本文字数： 897 阅读时长 ≈ 3 分钟

考点

  • 01背包
  • 位运算

思路

普通DP

对于每个数，有给它上正号还是负号两种选择，所以很自然地写DP转移如下

这里要注意，由于target可能是负数，所以所有数值都要向右平移1000个单位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int findTargetSumWays(vector<int>& nums, int target) {
    // 全部右移1000个单位, target的范围变为0 ~ 2000
    int n = nums.size();
    // f[i][j]: 前i个凑成和为j的个数
    int f[21][2001];
    memset(f, 0, sizeof(f));
    f[0][1000] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = 0; j <= 2000; ++j) {
        if (!f[i][j]) continue;
        // 对于考虑nums[i+1], 要么给它上正号，要么上负号
        if (j + x <= 2000) f[i + 1][j + nums[i]] += f[i][j];
        if (j - x >= 0) f[i + 1][j - nums[i]] += f[i][j];
      }
    }
    return f[n][target+1000];
  }
};

也可以滚动数组优化一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int findTargetSumWays(vector<int>& nums, int target) {
    // 全部右移1000个单位, target的范围变为0 ~ 2000
    int n = nums.size();
    // f[i][j]: 前i个凑成和为j的个数
    int f[2][2001];
    memset(f, 0, sizeof(f));
    f[0][1000] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      memset(f[i + 1 & 1], 0, sizeof(f[i + 1 & 1]));
      for (int j = 0; j <= 2000; ++j) {
        if (!f[i & 1][j]) continue;
        // 对于考虑nums[i+1], 要么给它上正号，要么上负号
        if (j + x <= 2000) f[i + 1 & 1][j + nums[i]] += f[i & 1][j];
        if (j - x >= 0) f[i + 1 & 1][j - nums[i]] += f[i & 1][j];
      }
    }
    return f[n & 1][target + 1000];
  }
};

01背包

将整个数组分为两个集合，一个会给正号，设它们的和为P，一个会给负号，设它们的和为N

显然，P + N= 数组和，P - N = target，那么必有P = (target + sum) / 2

其中P不能小于0，且不可能是小数，所以必定是偶数

那么问题就变成了01背包的裸题，从数组选某些数，看能否组成P的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int findTargetSumWays(vector<int>& nums, int target) {
    int s = 0, n = nums.size();
    for (int i = 0; i < n; ++i) s += nums[i];
    s += target;
    if (s < 0 || s & 1) return 0;
    int m = s >> 1, f[21][1001];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = 0; j <= m; ++j) {
        f[i + 1][j] += f[i][j];
        if (j + x <= m) f[i + 1][j + x] += f[i][j];
      }
    }
    return f[n][m];
  }
};

滚掉第一维，得到代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int findTargetSumWays(vector<int>& nums, int target) {
    int s = 0, n = nums.size();
    for (int i = 0; i < n; ++i) s += nums[i];
    s += target;
    if (s < 0 || s & 1) return 0;
    int m = s >> 1, f[1001];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = m; j >= 0; --j) {
        if (j + x <= m) f[j + x] += f[j];
      }
    }
    return f[m];
  }
};

扩展

如果这道题的数值范围扩大到1e9，就无法使用DP了，只能使用乘法原理

由于一共20个数字，210 = 1024，所以可以将数组分成两部分进行暴力枚举子集

左半部分用哈希表cnt1[x]记录值为x的个数c1，右半部分用哈希表cnt2[x]记录值为s - x的个数c2，

那么累加所有的c1 * cnt2[s - x]即为答案

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
class Solution {
 public:
  unordered_map<int, int> subset(vector<int> nums) {
    unordered_map<int, int> mp;
    int n = nums.size();
    for (int i = 0; i < (1 << n); ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if ((1 << j) & i) s += nums[j];
      }
      mp[s]++;
    }
    return mp;
  }
  int findTargetSumWays(vector<int>& nums, int target) {
    // 先去掉不可能情况
    int s = 0, n = nums.size();
    for (int i = 0; i < n; ++i) s += nums[i];
    s += target;
    if (s < 0 || s & 1) return 0;
    s >>= 1;
    // 乘法原理
    auto cnt1 = subset(vector<int>(nums.begin(), nums.begin() + n / 2));
    auto cnt2 = subset(vector<int>(nums.begin() + n / 2, nums.end()));
    int ans = 0;
    for (auto& [x, c1] : cnt1) {
      ans += c1 * cnt2[s - x];
    }
    return ans;
  }
};