Mind palace

some thoughts

0%

494. Target Sum

Posted on Edited on In Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

O(n*target)
把问题转换成真正的类背包问题
原来是每个数+或者-，现在每个数都乘2，这样就变成0个或者1个，也就是加这个数或者不加这个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S) return 0; // 所有数都加起来都到不了S，直接返回0
        for_each(nums.begin(), nums.end(), [](int &num){num <<= 1;});
        long target = sum + S; // 背包的目标值也要调整
        vector<vector<int>> f(target + 1, vector<int>(nums.size() + 1));
        f[0][0] = 1;
        for (int i = 0; i <= target; ++i) {
            for (int j = 1; j < f[i].size(); ++j) {
                f[i][j] = f[i][j - 1] + (i >= nums[j - 1] ? f[i - nums[j - 1]][j - 1] : 0);
            }
        }
        return f.back().back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S) return 0;
        for_each(nums.begin(), nums.end(), [](int &num){num <<= 1;});
        int target = sum + S, n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(target + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= target; ++j) {
            // for (int j = target; j >= 0; --j) {
                f[i][j] = f[i - 1][j] + (j >= nums[i - 1] ? f[i - 1][j - nums[i - 1]] : 0);
            }
        }
        return f[n][target];
    }
};

因为转换后的背包问题要求原来的所有数都要double，则新的target = sum + S也必须是个偶数，这样其实不需要修改nums，只需要把新的target除2即可，前提是target必须是偶数

  1. 原来的每个数放-1个或者1个转换成放0个或者2个
  2. 目标值从S变成sum + S，因为相当于在原来的每种可能基础上加了一个sum
  3. 这样相当于每个数都double了，进而变成标准0-1背包问题，即放这个数（原来的2倍）或者不放这个数
  4. 又因为原来的每个数要不是0个要不是2个，所以最后的目标值必须是偶数，所以可以不需要手动double每个数，仍然可以使用原来的数，只是目标值改成(sum + S) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = accumulate(nums.begin(), nums.end(), 0);
        long target = sum + S, n = nums.size();
        if (sum < S || target & 1) return 0; // 如果target不是偶数则得不到结果
        target >>= 1;
        vector<int> f(target + 1);
        f[0] = 1;
        for (int x : nums) {
            for (int t = target; t >= x; --t) { // 注意一维0-1背包一定要倒序
                f[t] += f[t - x];
            }
        }
        return f[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int target = sum + S, n = nums.size();
        if (sum < S || target & 1) return 0;
        target >>= 1;
        int f[target + 1] = {1};
        for (int i = 1; i <= n; ++i) {
            for (int j = target; j >= nums[i - 1]; --j) { // 注意一维0-1背包一定要倒序
                f[j] += f[j - nums[i - 1]];
            }
        }
        return f[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum < S) return 0;
        for_each(nums.begin(), nums.end(), [](int &num){num <<= 1;});
        int target = sum + S, n = nums.size();
        vector<int> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = target; j >= nums[i - 1]; --j) {
                f[j] += f[j - nums[i - 1]];
            }
        }
        return f[target];
    }
};

dp 不转换成背包直接建模，需要用到hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        vector<unordered_map<int, int>> f(n + 1);
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (auto &&[t, cnt] : f[i - 1]) {
                f[i][t + nums[i - 1]] += cnt;
                f[i][t - nums[i - 1]] += cnt;
            }
        }
        return f[n][S];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        unordered_map<int, int> f;
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            unordered_map<int, int> g;
            for (auto &&[t, cnt] : f) {
                g[t + nums[i - 1]] += cnt;
                g[t - nums[i - 1]] += cnt;
            }
            f = g;
        }
        return f[S];
    }
};