基本题目

416. 分割等和子集

0-1 背包问题，使用一维数组替代二维数组：从后向前更新即可

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (const int num : nums) sum += num;
        if (sum % 2) return false;
        sum /= 2;

        vector<int> available_sums(sum + 1, 0);
        available_sums[0] = 1;
        for (const int num : nums) {
            for (int i = sum; i >= num; i--)
                available_sums[i] |= available_sums[i - num];
            if (available_sums[sum]) return true;
        }

        return false;
    }
};

1049. 最后一块石头的重量 II

本问题等价于：将石头分为两组，求它们的和之间的最小差值

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0, target;
        for (const int w : stones) sum += w;
        target = sum / 2;

        vector<int> available_sums(target + 1, 0);
        available_sums[0] = 1;

        for (const int w : stones)
            for (int i = target; i >= w; i--)
                available_sums[i] = available_sums[i] | available_sums[i - w];
        
        for (int i = target; i >= 0; i--)
            if (available_sums[i])
                return sum - 2 * i;

        return 0;
    }
};

正确性证明：

每次粉碎时，记重量最大的石头所处的堆为 A（若两堆最大重量相同则任选一堆），另一堆为 B。从 A 中取出重量最大的石头，B 中任取一石头，若没有完全粉碎，则将新石头重新放入 A。这一操作从每堆石头中减去了同样的重量，从而保证重量之差的绝对值在粉碎前后是不变的。

若出现一堆没有石头，而另一堆不止一块石头的情况，记有石头的那一堆为 A，另一堆为 B。要继续粉碎，则需要从 A 中取出一块石头移入 B，然后按规则粉碎。但移入操作让重量之差的绝对值变得更小，与事实（已按照最小和差划分石头）矛盾，所以不会出现这种情况。

494. 目标和

dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]];

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size() == 1) return target == nums[0] || target == -nums[0];

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (target < -sum || target > sum) return 0;

        vector<vector<int>> possible_sums(nums.size(), vector<int>(2 * sum + 1, 0));
        possible_sums[0][sum + nums[0]]++;
        possible_sums[0][sum - nums[0]]++;

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j >= nums[i])
                    possible_sums[i][j] += possible_sums[i - 1][j - nums[i]];
                if (j <= 2 * sum - nums[i])
                    possible_sums[i][j] += possible_sums[i - 1][j + nums[i]];
            }
        }

        return possible_sums.back()[target + sum];
    }
};

注意到，如果将结果中的元素分为正、负，那么目标值可以表示为正和-负和，即总和-2*负和。因此在计算完总和后，只需要统计有多少种方式选出特定的元素，其和等于负和即可

dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (target < -sum || target > sum) return 0;
        if ((sum - target) % 2) return 0;
        sum = (sum - target) / 2;

        vector<int> possible_sums(sum + 1, 0);
        possible_sums[0]++;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = sum; j >= nums[i]; j--) {
                possible_sums[j] += possible_sums[j - nums[i]];
            }
        }
        return possible_sums[sum];
    }
};

474. 一和零

二维的 0-1 背包问题

class Solution {
public:
    void count(const string &str, int &m, int &n) {
        m = 0, n = 0;
        for (const char c : str)
            if (c == '0') m++;
            else n++;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int cm, cn;
        for (const string &str : strs) {
            count(str, cm, cn);
            for (int i = m; i >= cm; i--)
                for (int j = n; j >= cn; j--)
                    dp[i][j] = max(dp[i][j], dp[i - cm][j - cn] + 1);
        }
        return dp[m][n];
    }
};

518. 零钱兑换 II

0-n 背包问题

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (const int &coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 IV

0-n 背包问题的衍生问题：打乱顺序？

调整两层循环的顺序：对于不同的目标值，每次考虑当前序列的最后一个元素（求排列）。注意：该算法无法应对重复元素（去重）

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (const int &num: nums) {
                if (i >= num) dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
};

补充：原来的循环顺序：对于不同的元素，每次考虑与之前的元素结合组成目标值（求组合）

70. 爬楼梯（进阶版）

同组合总和 IV

class Solution {
public:
    int climbStairs(int n, int m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i >= j) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

322. 零钱兑换

统计最大数量的 0-n 背包问题

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX - 1);
        dp[0] = 0;
        for (const int &coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = min(dp[i - coin] + 1, dp[i]);
            }
        }
        return dp[amount] < INT_MAX - 1 ? dp[amount] : -1;
    }
};

279. 完全平方数

统计最大数量的 0-n 背包问题

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX - 1);
        dp[0] = 0;
        int sq;
        for (int i = 0;; i++) {
            if ((sq = i * i) > n) break;
            for (int j = sq; j <= n; j++) {
                dp[j] = min(dp[j], dp[j - sq] + 1);
            }
        }
        return dp[n];
    }
};

139. 单词拆分

类似于背包问题，添加前提——字符串匹配

class Solution {
public:
    struct Trie {
        bool terminal = false;
        unordered_map<char, Trie *> children;

        void addPath(const string &word) {
            Trie *tmp = this;
            for (const char c : word) {
                if (!tmp->children.count(c)) tmp->children[c] = new Trie();
                tmp = tmp->children[c];
            }
            tmp->terminal = true;
        }
    };

    bool matchDict(const string &s, int i, int j, Trie *trie) {
        for (int k = i; k < j; k++) {
            if (!trie->children.count(s[k])) return false;
            trie = trie->children[s[k]];
        }
        return trie->terminal;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        Trie *trie = new Trie();
        for (const string &word : wordDict) trie->addPath(word);

        vector<bool> match(s.size() + 1, false);    // s[0..i) can be segmented
        match[0] = true;
        for (int j = 1; j <= s.size(); j++) {
            for (int i = 0; i < j; i++) {
                match[j] = match[i] && matchDict(s, i, j, trie);
                if (match[j]) break;
            }
        }
        return match.back();
    }
};

考虑到字符串匹配的特殊性（跳过大多数匹配），可以尝试直接广度优先搜索（带剪枝）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        Trie *trie = new Trie();
        for (const string &word : wordDict) trie->addPath(word);

        vector<bool> checked(s.size(), false);
        queue<int> matchLen;
        matchLen.push(0);
        while (!matchLen.empty()) {
            int idx = matchLen.front();
            printf("%d\n", idx);
            matchLen.pop();

            // Insert all matching substrings into the queue
            Trie *tmp = trie;
            while (idx < s.size()) {
                char c = s[idx++];
                if (!tmp->children.count(c)) break;
                tmp = tmp->children[c];
                if (tmp->terminal) {
                    if (idx == s.size()) return true;
                    if (!checked[idx]) {
                        matchLen.push(idx);
                        checked[idx] = true;
                    }
                }
            }
        }
        return false;
    }
};