494.目标和

题目：https://leetcode.cn/problems/target-sum

0-1 背包回溯写法

考虑前 i 个物品的最大价值和，如果第 i 个物品还能放到背包里，那么前 i 个物品的最大价值和等于 max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i]) ，否则，为 dfs(i - 1, c)

    auto zero_one_knapsack(int capacity, vector<int> w, vector<int> v) -> int {
        int n = w.size();

        auto dfs = [&](this auto&& dfs, int i, int c) -> int {
            if (i < 0) {
                return 0;
            }
            if (c < w[i]) {
                return dfs(i - 1, c);
            }
            return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i]);
        };

        return dfs(n - 1, capacity);
    };

思路

先食用 【0-1背包 完全背包【基础算法精讲 18】-哔哩哔哩】

先做一波转换，题目就改为考虑：从 nums 选择一些数，使得和为 m，这是 0/1 subset sum问题。（m 为(s+target)/2 和 (s-target)/2）取较小值。

回溯不带记忆化搜索的版本

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = reduce(nums.begin(), nums.end()) - abs(target);
        if (s < 0 || s % 2 != 0) {
            return 0;
        }

        int m = s / 2;
        int n = nums.size();
        
        auto dfs = [&](this auto&& dfs, int i, int c) -> int {

            if (i < 0) {
                return c == 0 ? 1 : 0;
            }

            if (c < nums[i]) {
                return dfs(i - 1, c);
            }
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i]);
        };

        return dfs(n - 1, m);

    }
};

回溯带记忆化搜索的版本

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = reduce(nums.begin(), nums.end()) - abs(target);
        if (s < 0 || s % 2 != 0) {
            return 0;
        }

        int m = s / 2;
        int n = nums.size();
        vector<vector<int>> memo(n, vector<int>(m + 1, -1));
        
        auto dfs = [&](this auto&& dfs, int i, int c) -> int {

            if (i < 0) {
                return c == 0 ? 1 : 0;
            }

            int& res = memo[i][c];
            if (res != -1) {
                return res;
            }

            if (c < nums[i]) {
                return res = dfs(i - 1, c);
            }
            return res = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);
        };

        return dfs(n - 1, m);

    }
};

回溯改递推

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = reduce(nums.begin(), nums.end()) - abs(target);
        if (s < 0 || s % 2 != 0) {
            return 0;
        }

        int m = s / 2;
        int n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        f[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= m; c++) {
                if (c < nums[i]) {
                    f[i + 1][c] = f[i][c];
                } else {
                    f[i + 1][c] = f[i][c] + f[i][c - nums[i]];
                }
            }
        }
        return f[n][m];
    }
};

优化为滚动数组，添加一个 %2 就好

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = reduce(nums.begin(), nums.end()) - abs(target);
        if (s < 0 || s % 2 != 0) {
            return 0;
        }

        int m = s / 2;
        int n = nums.size();
        vector<vector<int>> f(2, vector<int>(m + 1));
        f[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= m; c++) {
                if (c < nums[i]) {
                    f[(i + 1) % 2][c] = f[i % 2][c];
                } else {
                    f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - nums[i]];
                }
            }
        }
        return f[n % 2][m];
    }
};

---

以下是错误思路，仅保留

dfs(i) 表示考虑前 i 个满足答案的数目，它可以由dfs(i - 1, t-nums[i]) 和 dfs(i - 1, t+nums[i]) 得到。当考虑前0个满足答案的数目时，也就是dfs(0) ，容易得到结果就是等于正的或者负的 t。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        auto dfs = [&](this auto&& dfs, int i, int t) -> int {
            if (i == 0) {
                return (t == -nums[0] ? 1 : 0) + (t == nums[0] ? 1 : 0);
            }
            return dfs(i - 1, t - nums[i]) + dfs(i - 1, t + nums[i]);
        };
        return dfs(n - 1, target);
    }
};

考虑回溯改递推，发现不好改为递推的数组形式……