0
已解决
新手启示者
题目描述 Description
素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。现给定一个正整数n，求将其分解成若干个素数之和的方案总数。
输入描述 Input Description
一行：一个正整数n
输出描述 Output Description
一行：一个整数表示方案总数
样例输入 Sample Input
7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例解释】
7=7 7=2+5
7=2+2+3
【福利数据】
【输入】 20
【输出】 26
【数据范围及约定】
对于30%的数据 1<=n<=10
对于100%的数据，1<=n<=10^3
大佬们，是时候展现真正的技术了！
汪宇航在2021-05-22 20:01:00追加了内容
¥dd
0
已采纳
中级启示者
完全背包求方案总数
可以把n看成背包容量，不大于n的所有素数看成物品，即可把问题转化成一个完全背包问题
状态转移方程
f[j]+=f[j-a[i]];//a[i]是第i个素数最后的结果就是f[n]
举个例子：
模拟一下7质因数分解
f[0]=1//初始化
f[1]=0//1不能被任何质数分解
f[2]=1//2能被2分解
f[3]=1//被3分解
f[4]=1//被2分解
f[5]=2//这里就是重点了，5能被5分解，也能被2，3分解注意边界条件f[0]=1
0
新手启示者
dingdingding
@
@@
@@@
@@@@
@@@@@
@@@@@@
@@@@@@@
@@@@@@@@
0
新手启示者
@赵逸凡 @陈曦 @李瑞曦
@曹博扬 @汪恺恒
@谭迪元
0
新手启示者
@赵睿泽
0
新手启示者
@cdt
@酷町堂
