完全背包的计数问题

引例

题目描述：输入一个n，输出n的所有组成方案，例如：

n=4,有

4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;

5种方案。

接下来升级一下

正题

如题 洛谷P2563——质数和分解

此题就需要将完全背包变形一下

原本完全背包的转移方程为
(f(j) = max( f(j), f(j-v[i])+w[i] ))

若是求计数问题 则变为
(f(j) = f(j)+f( j-v[i] ))

即变为
(f(j) += f( j-v[i] ))

(f(j)) 表示能拼成j的方案数

(f( j ) += f( j-v[i] )) 的意思是j可以由 j-v[i] 加上一个 v[i] 拼凑成
（In other words： j可以由某个数加上一个素数组成），而f(j-v[i])又可由某个数加上一个素数组成，而在此过程中，也就是方案的累加。

注意初始化 f(0) = 1

此转移方程可以和朴素背包一样表示为二维状态：如下：

(f(i, j))表示前i个素数里面能拼成j的方案数

注意初始化f[0][0] = 1