这道问题我最早是在某次面试中见到的.它的代码量非常小但涉及的知识点非常多,十分适合作为面试题考察面试者的算法水平.

题目1

给定$N$种物品,第$i$种物品重量为$v_i$,数量为$c_i$.
记$f(i,j)$为不使用第$i$种物品时总重量为$j$的方案数,两种方案不同当且仅当至少有一种物品在两种方案里出现数量不同.
对每个$i=1,2,\cdots ,N$和$j=1,2,\cdots ,M$,求$f(i,j)$,要求时间复杂度为$O(NM)$,空间复杂度为$O(M)$.
这里为了方便可以认为加减运算是$O(1)$的,实际上通常这类问题会对某个数进行取模运算.

在尝试解决题目1之前,先来看一个简化版本的问题:

题目2

给定$N$种物品,第$i$种物品重量为$v_i$,数量为$c_i$.
对每个$j=1,2,\cdots ,M$,求总重量为$j$的方案数.

记$DP(i,j)$为考虑到前$i$个物品时总重量为$j$的方案数.
$DP(i,j)=\sum _{k=0}^{\min (c_i,\lfloor \frac{j}{v_i}\rfloor )}DP(i-1,j-k{v}_i)$.
直接按公式进行计算,时间复杂度为$O(N{M}^2)$,空间复杂度为$O(NM)$.

注意到$DP(i,j)$只会由满足$j$与$k$模$v_i$同余的$DP(i-1,k)$转移.
实际上$DP(i,j)$是$k$满足同余条件的$DP(i-1,k)$中某段区间的和.
因此使用前缀和可以将每个状态转移优化到$O(1)$,总的时间复杂度为$O(NM)$.

注意到$DP(i,j)$只会从满足$k\le j$的$DP(i-1,k)$转移,因此可以将空间优化到$O(M)$.

代码:

//dp : a array of zeros longer than M
dp[0] = 1;
for(int i = 1; i <= N; i += 1){
    for(int j = v[i]; j <= M; j += 1) dp[j] += dp[j - v[i]]; //prefix sum
    for(int j = M; j >= (c[i] + 1) * v[i]; j -= 1) dp[j] -= dp[j - (c[i] + 1) * v[i]];
}

在已经得到题目2中的答案后,回到题目1.
仔细观察题目2中的代码,在得到$i=N$时的$dp$数组的情况下,可以将操作反向进行,重新得到在$i=N-1$时的dp数组.
并且无论以何种顺序遍历物品,所得到的dp数组肯定都是一样的,因此可以将任何一个物品从dp数组中移除,于是可以在与题目2同样复杂度的情况下解决题目1.
代码:

//dp: answer to problem 2
//tmp: another array longer than M
for(int i = 1; i <= N; i += 1){
    for(int j = 0; j <= M; j += 1) tmp[j] = dp[j];
    for(int j = (c[i] + 1) * v[i]; j <= M; j += 1) tmp[j] += tmp[j - (c[i] + 1) * v[i]];
    for(int j = M; j >= v[i]; j -= 1) tmp[j] -= tmp[j - v[i]];
    //now, tmp[j] is f(i, j)
}