第 24 站 · 动态规划

背包与组合计数

0/1 背包倒序，完全背包正序 O(n × target)

周赛难度分难度分 2092–难度分 2204· 中位难度分 2148（2/10 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 24 站 · 10 题

先学: 动规入门
学完去: 没有后续站依赖它。
面试频次: 5 家公司考过 · 面经出现 5 次Airbnb 1、Amazon 1、Pinterest 1、Squarepoint 1、WorldQuant 1

先做这道

LC 322零钱兑换中等

卡住再看

掌握完全背包最少选取数，处理不可达状态和金额零。

要点

0/1 背包倒序遍历容量，保证 dp[s-x] 还是「没用过 x」的旧值；完全背包正序遍历，允许同一件物品重复使用。
物品在外层、容量在内层，数的是组合（不计顺序）；容量在外层、物品在内层，数的是排列。
很多题要先转化成背包：「分成两个和相等的子集」= 能否凑出 sum/2；「目标和」= 凑出 (sum+target)/2。

易错点

0/1 背包写成正序，同一件物品会被用很多次。
计数问题 dp[0] = 1（什么都不选也是一种方案）；求最值问题 dp[0] = 0，其余初始化为无穷。
转化成 (sum+target)/2 之前没检查奇偶性和正负，会得到错误的下标。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

动态规划 · 零钱兑换

硬币 1、3、4，每种无限枚，凑出 6

换个输入

0dp[0]

∞dp[1]

∞dp[2]

∞dp[3]

∞dp[4]

∞dp[5]

∞dp[6]

当前处理已发现 / 已计算答案

目标金额: 6
当前金额: —
最少硬币: 尚不可达

dp[0] = 0，其余状态为 ∞（不可达）。dp[x] 表示凑出金额 x 的最少硬币数。

速度

步骤 1 / 15

始终成立按金额递增计算；更新 dp[x] 时，所有更小金额的最优解都已确定。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 322。

Python

def count_subsets(nums: list[int], target: int) -> int:
    """Ways to pick a subset (each item at most once) that sums to target."""
    dp = [1] + [0] * target  # dp[s]: ways to reach sum s
    for x in nums:
        for s in range(target, x - 1, -1):  # backwards: x is used at most once
            dp[s] += dp[s - x]
    return dp[target]


def count_combinations(coins: list[int], amount: int) -> int:
    """Ways to make amount with unlimited coins, order ignored."""
    dp = [1] + [0] * amount
    for coin in coins:  # coins outside: each multiset is counted once
        for s in range(coin, amount + 1):  # forwards: a coin may be reused
            dp[s] += dp[s - coin]
    return dp[amount]

C++

// Ways to pick a subset (each item at most once) that sums to target.
long long countSubsets(const vector<int>& nums, int target) {
    vector<long long> dp(target + 1, 0);  // dp[s]: ways to reach sum s
    dp[0] = 1;
    for (int x : nums)
        for (int s = target; s >= x; s--) dp[s] += dp[s - x];  // backwards: x used at most once
    return dp[target];
}

// Ways to make amount with unlimited coins, order ignored.
long long countCombinations(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins)  // coins outside: each multiset is counted once
        for (int s = coin; s <= amount; s++) dp[s] += dp[s - coin];  // forwards: reuse allowed
    return dp[amount];
}

Java

class Solution {
    // Ways to pick a subset (each item at most once) that sums to target.
    long countSubsets(int[] nums, int target) {
        long[] dp = new long[target + 1]; // dp[s]: ways to reach sum s
        dp[0] = 1;
        for (int x : nums)
            for (int s = target; s >= x; s--) dp[s] += dp[s - x]; // backwards: x used at most once
        return dp[target];
    }

    // Ways to make amount with unlimited coins, order ignored.
    long countCombinations(int[] coins, int amount) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int coin : coins) // coins outside: each multiset is counted once
            for (int s = coin; s <= amount; s++) dp[s] += dp[s - coin]; // forwards: reuse allowed
        return dp[amount];
    }
}

// countSubsets returns the ways to pick a subset (each item at most once) that sums to target.
func countSubsets(nums []int, target int) int {
	dp := make([]int, target+1) // dp[s]: ways to reach sum s
	dp[0] = 1
	for _, x := range nums {
		for s := target; s >= x; s-- { // backwards: x is used at most once
			dp[s] += dp[s-x]
		}
	}
	return dp[target]
}

// countCombinations returns the ways to make amount with unlimited coins, order ignored.
func countCombinations(coins []int, amount int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, coin := range coins { // coins outside: each multiset is counted once
		for s := coin; s <= amount; s++ { // forwards: a coin may be reused
			dp[s] += dp[s-coin]
		}
	}
	return dp[amount]
}

常见变体

这一站的题还会用到下面 6 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

变体矩阵：每格写的是决定这一格的那一两行代码
	最大价值	组合数	排列数	能否凑出	最少件数
0/1 背包（每件最多一次）	0/1 背包求最大价值`for c in range(cap, w - 1, -1): dp[c] = max(dp[c], dp[c - w] + v)for (int c = cap; c >= weights[i]; c--) dp[c] = max(dp[c], dp[c - weights[i]] + values[i]);for (int c = cap; c >= weights[i]; c--) dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);for c := capacity; c >= w; c-- { dp[c] = max(dp[c], dp[c-w]+values[i])`	主模板`for s in range(target, x - 1, -1): dp[s] += dp[s - x]for (int s = target; s >= x; s--) dp[s] += dp[s - x];for (int s = target; s >= x; s--) dp[s] += dp[s - x];for s := target; s >= x; s-- { dp[s] += dp[s-x]`	每件只能用一次又讲顺序，就不是背包循环了：先数出凑成目标的子集，再按每个子集的大小乘上排列数，面试很少这样问。	0/1 背包判断能否凑出`for s in range(target, x - 1, -1): dp[s] = dp[s] or dp[s - x]for (int s = target; s >= x; s--) dp[s] = dp[s] \|\| dp[s - x];for (int s = target; s >= x; s--) dp[s] = dp[s] \|\| dp[s - x];for s := target; s >= x; s-- { dp[s] = dp[s] \|\| dp[s-x]`	沿用「能否凑出」的倒序循环，状态换成件数：dp[0] = 0，其余为无穷大，转移 dp[s] = min(dp[s], dp[s - x] + 1)。
完全背包（无限次）	和 0/1 最大价值是同一行转移，只把容量循环改成正序，同一件物品就能被反复选。	主模板`for s in range(coin, amount + 1): dp[s] += dp[s - coin]for (int s = coin; s <= amount; s++) dp[s] += dp[s - coin];for (int s = coin; s <= amount; s++) dp[s] += dp[s - coin];for s := coin; s <= amount; s++ { dp[s] += dp[s-coin]`	完全背包求排列数`for s in range(1, target + 1): for x in nums:for (int s = 1; s <= target; s++) for (int x : nums)for (int s = 1; s <= target; s++) for (int x : nums)for s := 1; s <= target; s++ { for _, x := range nums {`	看组合数是否大于 0 即可；只要真假时把 += 换成 or。LC 139 单词拆分是带顺序的同类题：和放外层，单词放内层。	完全背包求最少件数`for s in range(coin, amount + 1): dp[s] = min(dp[s], dp[s - coin] + 1)for (int s = coin; s <= amount; s++) dp[s] = min(dp[s], dp[s - coin] + 1);for (int s = coin; s <= amount; s++) dp[s] = Math.min(dp[s], dp[s - coin] + 1);for s := coin; s <= amount; s++ { dp[s] = min(dp[s], dp[s-coin]+1)`
多重背包（二进制拆分）	多重背包：二进制拆分成 0/1`take = min(k, cnt) dp[c] = max(dp[c], dp[c - take * w] + take * v)int take = min(k, cnt); dp[c] = max(dp[c], dp[c - take * w] + take * v);int take = Math.min(k, cnt); dp[c] = Math.max(dp[c], dp[c - take * w] + take * v);take := min(k, cnt) dp[c] = max(dp[c], dp[c-takew]+takev)`	计数不能二进制拆分：拆出的包可能一样大（5 = 1 + 2 + 2），同一个件数会被数两次。改为对每种物品枚举取 0 到 cnt 件，或用前缀和把这层枚举优化掉。	件数有限又讲顺序时，一维的背包状态记不住每种物品已经用了几件，要换成多重集排列计数，面试很少见。	可行性不怕重复计数：二进制拆分后，照 0/1「能否凑出」那一格的倒序 or 来做。	拆分后每包算 take 件：dp[c] = min(dp[c], dp[c - take * w] + take)。

0/1 背包求最大价值时间 O(n × cap) · 空间 O(cap)

每件物品只能选一次、容量有上限、要价值最大：倒序枚举容量，取 max。LC 1049 最后一块石头的重量 II 就是把石头重量同时当作重量和价值，求不超过总和一半的最大和。

Python

def knapsack_01(weights: list[int], values: list[int], cap: int) -> int:
    """Best total value within capacity cap, each item at most once."""
    dp = [0] * (cap + 1)  # dp[c]: best value with capacity c
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):  # backwards: the item is used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

C++

// Best total value within capacity cap, each item at most once.
int knapsack01(const vector<int>& weights, const vector<int>& values, int cap) {
    vector<int> dp(cap + 1, 0);  // dp[c]: best value with capacity c
    for (size_t i = 0; i < weights.size(); i++)
        for (int c = cap; c >= weights[i]; c--)  // backwards: item i is used at most once
            dp[c] = max(dp[c], dp[c - weights[i]] + values[i]);
    return dp[cap];
}

Java

class Solution {
    // Best total value within capacity cap, each item at most once.
    int knapsack01(int[] weights, int[] values, int cap) {
        int[] dp = new int[cap + 1]; // dp[c]: best value with capacity c
        for (int i = 0; i < weights.length; i++)
            for (int c = cap; c >= weights[i]; c--) // backwards: item i is used at most once
                dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
        return dp[cap];
    }
}

// knapsack01 returns the best total value within capacity cap, each item at most once.
func knapsack01(weights, values []int, capacity int) int {
	dp := make([]int, capacity+1) // dp[c]: best value with capacity c
	for i, w := range weights {
		for c := capacity; c >= w; c-- { // backwards: item i is used at most once
			dp[c] = max(dp[c], dp[c-w]+values[i])
		}
	}
	return dp[capacity]
}

0/1 背包判断能否凑出时间 O(n × target) · 空间 O(target)

只问「能不能」、不问方案数或价值：状态换成布尔值，转移用 or。LC 416 分割等和子集先判断总和奇偶，再看能否凑出一半。

Python

def can_partition(nums: list[int]) -> bool:
    """Can nums be split into two groups with equal sums?"""
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target  # dp[s]: some subset sums to s
    for x in nums:
        for s in range(target, x - 1, -1):  # backwards: x is used at most once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

C++

// Can nums be split into two groups with equal sums?
bool canPartition(const vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2) return false;
    int target = total / 2;
    vector<char> dp(target + 1, false);  // dp[s]: some subset sums to s
    dp[0] = true;
    for (int x : nums)
        for (int s = target; s >= x; s--)  // backwards: x is used at most once
            dp[s] = dp[s] || dp[s - x];
    return dp[target];
}

Java

class Solution {
    // Can nums be split into two groups with equal sums?
    boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1]; // dp[s]: some subset sums to s
        dp[0] = true;
        for (int x : nums)
            for (int s = target; s >= x; s--) // backwards: x is used at most once
                dp[s] = dp[s] || dp[s - x];
        return dp[target];
    }
}

// canPartition reports whether nums can be split into two groups with equal sums.
func canPartition(nums []int) bool {
	total := 0
	for _, x := range nums {
		total += x
	}
	if total%2 != 0 {
		return false
	}
	target := total / 2
	dp := make([]bool, target+1) // dp[s]: some subset sums to s
	dp[0] = true
	for _, x := range nums {
		for s := target; s >= x; s-- { // backwards: x is used at most once
			dp[s] = dp[s] || dp[s-x]
		}
	}
	return dp[target]
}

完全背包求最少件数时间 O(n × amount) · 空间 O(amount)

物品可以无限取、要凑出的件数最少：正序枚举容量，dp 初值用「无穷大」，转移取 min(dp[s], dp[s - coin] + 1)。LC 322 零钱兑换和 LC 279 完全平方数都是这个形状。

Python

def min_coins(coins: list[int], amount: int) -> int:
    """Fewest coins (each reusable) that sum to amount, or -1."""
    INF = amount + 1  # more coins than any answer can need
    dp = [0] + [INF] * amount  # dp[s]: fewest coins for sum s
    for coin in coins:
        for s in range(coin, amount + 1):  # forwards: the coin may be reused
            dp[s] = min(dp[s], dp[s - coin] + 1)
    return dp[amount] if dp[amount] < INF else -1

C++

// Fewest coins (each reusable) that sum to amount, or -1.
int minCoins(const vector<int>& coins, int amount) {
    const int INF = amount + 1;  // more coins than any answer can need
    vector<int> dp(amount + 1, INF);  // dp[s]: fewest coins for sum s
    dp[0] = 0;
    for (int coin : coins)
        for (int s = coin; s <= amount; s++)  // forwards: the coin may be reused
            dp[s] = min(dp[s], dp[s - coin] + 1);
    return dp[amount] < INF ? dp[amount] : -1;
}

Java

class Solution {
    // Fewest coins (each reusable) that sum to amount, or -1.
    int minCoins(int[] coins, int amount) {
        final int INF = amount + 1; // more coins than any answer can need
        int[] dp = new int[amount + 1]; // dp[s]: fewest coins for sum s
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int coin : coins)
            for (int s = coin; s <= amount; s++) // forwards: the coin may be reused
                dp[s] = Math.min(dp[s], dp[s - coin] + 1);
        return dp[amount] < INF ? dp[amount] : -1;
    }
}

// minCoins returns the fewest coins (each reusable) that sum to amount, or -1.
func minCoins(coins []int, amount int) int {
	inf := amount + 1 // more coins than any answer can need
	dp := make([]int, amount+1) // dp[s]: fewest coins for sum s
	for s := 1; s <= amount; s++ {
		dp[s] = inf
	}
	for _, coin := range coins {
		for s := coin; s <= amount; s++ { // forwards: the coin may be reused
			dp[s] = min(dp[s], dp[s-coin]+1)
		}
	}
	if dp[amount] < inf {
		return dp[amount]
	}
	return -1
}

完全背包求排列数时间 O(n × target) · 空间 O(target)

顺序不同算不同方案（1+2 和 2+1 是两种）：把「和」放在外层、物品放在内层，每个和都试一遍最后一步选谁。LC 377 组合总和 IV 名字叫组合，算的其实是排列数。

Python

def count_sequences(nums: list[int], target: int) -> int:
    """Ordered ways to reach target with unlimited reuse: (1, 2) and (2, 1) differ."""
    dp = [1] + [0] * target  # dp[s]: sequences that sum to s
    for s in range(1, target + 1):  # sums outside: each sum tries every last pick
        for x in nums:
            if x <= s:
                dp[s] += dp[s - x]
    return dp[target]

C++

// Ordered ways to reach target with unlimited reuse: (1, 2) and (2, 1) differ.
long long countSequences(const vector<int>& nums, int target) {
    vector<long long> dp(target + 1, 0);  // dp[s]: sequences that sum to s
    dp[0] = 1;
    for (int s = 1; s <= target; s++)  // sums outside: each sum tries every last pick
        for (int x : nums)
            if (x <= s) dp[s] += dp[s - x];
    return dp[target];
}

Java

class Solution {
    // Ordered ways to reach target with unlimited reuse: (1, 2) and (2, 1) differ.
    long countSequences(int[] nums, int target) {
        long[] dp = new long[target + 1]; // dp[s]: sequences that sum to s
        dp[0] = 1;
        for (int s = 1; s <= target; s++) // sums outside: each sum tries every last pick
            for (int x : nums)
                if (x <= s) dp[s] += dp[s - x];
        return dp[target];
    }
}

// countSequences returns the ordered ways to reach target with unlimited reuse.
func countSequences(nums []int, target int) int {
	dp := make([]int, target+1) // dp[s]: sequences that sum to s
	dp[0] = 1
	for s := 1; s <= target; s++ { // sums outside: each sum tries every last pick
		for _, x := range nums {
			if x <= s {
				dp[s] += dp[s-x]
			}
		}
	}
	return dp[target]
}

二维费用 0/1 背包时间 O(len × m × n) · 空间 O(m × n)

每件物品同时消耗两种资源（比如 0 的个数和 1 的个数）：状态加一维，两个容量都倒序。LC 474 一和零是求最多件数；LC 879 盈利计划是同样的两维再加计数。

Python

def max_strings(strs: list[str], m: int, n: int) -> int:
    """Most strings you can pick with at most m zeros and n ones in total."""
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j]: best with i zeros, j ones
    for s in strs:
        zeros, ones = s.count("0"), s.count("1")
        for i in range(m, zeros - 1, -1):  # both capacities backwards: s is used once
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
    return dp[m][n]

C++

// Most strings you can pick with at most m zeros and n ones in total.
int maxStrings(const vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));  // dp[i][j]: best with i zeros, j ones
    for (const string& s : strs) {
        int zeros = count(s.begin(), s.end(), '0'), ones = (int)s.size() - zeros;
        for (int i = m; i >= zeros; i--)  // both capacities backwards: s is used once
            for (int j = n; j >= ones; j--)
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
    }
    return dp[m][n];
}

Java

class Solution {
    // Most strings you can pick with at most m zeros and n ones in total.
    int maxStrings(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j]: best with i zeros, j ones
        for (String s : strs) {
            int zeros = (int) s.chars().filter(c -> c == '0').count(), ones = s.length() - zeros;
            for (int i = m; i >= zeros; i--) // both capacities backwards: s is used once
                for (int j = n; j >= ones; j--)
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
        }
        return dp[m][n];
    }
}

import "strings"

// maxStrings returns the most strings you can pick with at most m zeros and n ones.
func maxStrings(strs []string, m, n int) int {
	dp := make([][]int, m+1) // dp[i][j]: best with i zeros, j ones
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for _, s := range strs {
		zeros := strings.Count(s, "0")
		ones := len(s) - zeros
		for i := m; i >= zeros; i-- { // both capacities backwards: s is used once
			for j := n; j >= ones; j-- {
				dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
			}
		}
	}
	return dp[m][n]
}

多重背包：二进制拆分成 0/1时间 O(cap × Σ log cnt) · 空间 O(cap)

第 i 种物品最多 counts[i] 件：按 1、2、4…件打包，剩下的再成一包，每包当一件 0/1 物品，复杂度从 O(cap × Σcnt) 降到 O(cap × Σlog cnt)。只适合求最大价值或可行性；计数会把同一件数数两次（5 = 1 + 2 + 2）。站内题没有直接考它，周赛和 OA 偶尔出现。

Python

def bounded_knapsack(weights: list[int], values: list[int], counts: list[int], cap: int) -> int:
    """Best value within cap when item i has counts[i] copies."""
    dp = [0] * (cap + 1)
    for w, v, cnt in zip(weights, values, counts):
        k = 1
        while cnt > 0:  # bundles of 1, 2, 4, ... copies, then the rest
            take = min(k, cnt)
            cnt -= take
            k *= 2
            for c in range(cap, take * w - 1, -1):  # each bundle is one 0/1 item
                dp[c] = max(dp[c], dp[c - take * w] + take * v)
    return dp[cap]

C++

// Best value within cap when item i has counts[i] copies.
int boundedKnapsack(const vector<int>& weights, const vector<int>& values, const vector<int>& counts, int cap) {
    vector<int> dp(cap + 1, 0);
    for (size_t i = 0; i < weights.size(); i++) {
        int w = weights[i], v = values[i], cnt = counts[i];
        for (int k = 1; cnt > 0; k *= 2) {  // bundles of 1, 2, 4, ... copies, then the rest
            int take = min(k, cnt);
            cnt -= take;
            for (int c = cap; c >= take * w; c--)  // each bundle is one 0/1 item
                dp[c] = max(dp[c], dp[c - take * w] + take * v);
        }
    }
    return dp[cap];
}

Java

class Solution {
    // Best value within cap when item i has counts[i] copies.
    int boundedKnapsack(int[] weights, int[] values, int[] counts, int cap) {
        int[] dp = new int[cap + 1];
        for (int i = 0; i < weights.length; i++) {
            int w = weights[i], v = values[i], cnt = counts[i];
            for (int k = 1; cnt > 0; k *= 2) { // bundles of 1, 2, 4, ... copies, then the rest
                int take = Math.min(k, cnt);
                cnt -= take;
                for (int c = cap; c >= take * w; c--) // each bundle is one 0/1 item
                    dp[c] = Math.max(dp[c], dp[c - take * w] + take * v);
            }
        }
        return dp[cap];
    }
}

// boundedKnapsack returns the best value within capacity when item i has counts[i] copies.
func boundedKnapsack(weights, values, counts []int, capacity int) int {
	dp := make([]int, capacity+1)
	for i, w := range weights {
		v, cnt := values[i], counts[i]
		for k := 1; cnt > 0; k *= 2 { // bundles of 1, 2, 4, ... copies, then the rest
			take := min(k, cnt)
			cnt -= take
			for c := capacity; c >= take*w; c-- { // each bundle is one 0/1 item
				dp[c] = max(dp[c], dp[c-take*w]+take*v)
			}
		}
	}
	return dp[capacity]
}

为什么对

0/1 背包容量倒序：更新 dp[s] 时 dp[s−x] 本轮还没被改过，仍是不含物品 x 的值，所以 x 最多用一次；正序时 dp[s−x] 可能已经用过 x，物品会被重复使用，这正是完全背包需要的。
物品在外层时，每种组合只按物品顺序被数一次，得到组合数；容量在外层时，每一步都可以让任意物品当最后一个，不同顺序分别计数，得到排列数。例如硬币 {1, 2, 3} 凑 5：组合 5 种，排列 13 种。
目标和的归约：设加正号的数之和为 P，则 P − (sum − P) = target，P = (sum + target) / 2，所以还要求 sum + target 是非负偶数。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

背包问题我用一维数组 dp[s]。0/1 背包容量倒着循环，这样 dp[s − x] 还是没放这个物品时的值，每个物品最多用一次；完全背包正着循环，允许重复使用。计数时，物品在外层得到组合数，容量在外层得到排列数。很多题能归约成背包，比如分割等和子集就是问 sum/2 能不能凑出来。复杂度 O(n × 容量)。

English

For knapsacks I use a one-dimensional dp over capacity. The 0/1 version loops capacity downwards so dp[s − x] still excludes the current item, using each item at most once, and the unbounded version loops upwards to allow reuse. When counting, items in the outer loop count combinations and capacity in the outer loop counts permutations. Many problems reduce to this, for example equal-sum partition asks whether half the total is reachable, all in O(n × capacity).

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

0/1 背包容量倒序：更新 dp[s] 时 dp[s−x] 本轮还没被改过，仍是不含物品 x 的值，所以 x 最多用一次；正序时 dp[s−x] 可能已经用过 x，物品会被重复使用，这正是完全背包需要的。
物品在外层时，每种组合只按物品顺序被数一次，得到组合数；容量在外层时，每一步都可以让任意物品当最后一个，不同顺序分别计数，得到排列数。例如硬币 {1, 2, 3} 凑 5：组合 5 种，排列 13 种。
目标和的归约：设加正号的数之和为 P，则 P − (sum − P) = target，P = (sum + target) / 2，所以还要求 sum + target 是非负偶数。

小测

4 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。去 OA 选择题练习

4 道题

0/1 背包压成一维时写作 for w in range(W, wt - 1, -1): dp[w] = max(dp[w], dp[w - wt] + val)。为什么容量要从大到小遍历？
- 从小到大会越界
- 从大到小更快
- 保证 dp[w - wt] 还是放这件物品之前的值，每件物品最多用一次
- 为了让 dp[0] 保持为 0
0/1 背包的 O(n·W) 动态规划通常被称为「伪多项式时间」，原因是？
- W 是一个数值，写成二进制只要 log W 位；O(n·W) 对输入长度来说是指数级的
- 它只在 n 较小时才是多项式
- 它用了随机化
- 它的空间是指数级的
硬币 coins = [1, 2]，金额 3。执行 ways = [1, 0, 0, 0]；for c in coins: for a in range(c, 4): ways[a] += ways[a - c]。ways[3] 是多少？
- 4
- 3
- 2
- 1

items 有 n 件物品，容量是 W。时间复杂度是？

def knapsack(items, W):
    dp = [0] * (W + 1)
    for wt, val in items:
        for w in range(W, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

O(2^n)
O(n log W)
O(n·W)
O(n + W)

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

def count_subsets(nums: list[int], target: int) -> int:

    return dp[amount]

分档练习

本站在 500 路里的 10 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 7

#	题目	一句话思路	难度分
322	零钱兑换	掌握完全背包最少选取数，处理不可达状态和金额零。
279	完全平方数	把平方数生成规则转为完全背包物品，练习从题意识别最少次数模型。
518	零钱兑换 II	通过外层遍历物品避免重复计算排列，明确组合计数的循环顺序。
377	组合总和 Ⅳ	与零钱兑换II对照，解释为什么先遍历目标和会统计有序序列。
416	分割等和子集	将等和划分转成0/1背包可达性，解释容量倒序以防重复使用元素。
494	目标和	用代数变换将正负号分配化为子集计数，正确处理零和奇偶条件。
1049	最后一块石头的重量 II	把反复碰撞转成两组重量差最小，训练看穿过程并抽象成子集问题。	难度分 2092

进阶 3

#	题目	一句话思路	难度分
474	一和零	在两个容量维度上做0/1背包，说明双重倒序和资源约束。
879	盈利计划	将超过目标的收益合并到同一状态，练习多约束计数与状态范围压缩。	难度分 2204
691	贴纸拼词	用剩余字符需求或位掩码表示状态，训练记忆化搜索、去重和不可达判断。

本站 OA 真题 5

Maximize Product of Sizes of SubtreesAmazon
Get Minimum TimeMicrosoft
Maximize Number of Produced CarsMicrosoft
Selecting StocksSnowflake
Reach Target BalanceConfluent

全部 5 道