由于每个数字可以选无数次，可以类比完全背包，最外层枚举当前放哪个质数，内层按照完全背包的顺序枚举，在循环过程中每次按照顺序考虑放哪个质数（放完之后就不再重复考虑，所以自然就是没有重复的）。
值得注意的是，初始化 dp[0] = 1，不能初始化成每个dp[prime(表示一个质数）] = 1，因为会重复考虑。
转移的时候由于方案数根据加法原理可得转移：dp[j] += dp[j - prime[i] ] ;
#include<bits/stdc++.h> using namespace std; int prime[105],cnt=1; int n; int dp[205]; bool vis[205]; void pre() { prime[1]=2; vis[2]=1; for(int i=3;i<=201;i++) { int sq=sqrt(i),flag=0; for(int j=2;j<=sq;j++) { if(i%j==0) { flag=1; break; } } if(!flag) prime[++cnt]=i,vis[i]=1; } } int tr(int p){ int i; for(i=2;i<=p;i++) for(int j=2;j<=p/i;j++) vis[i*j]=1; } int dfs(int now) { if(now==0) return 0; if(dp[now]&&dp[now]!=1) return dp[now]; for(int i=1;i<=cnt&&prime[i]<=now;i++) dp[now]+=dfs(now-prime[i]); return dp[now]; } int main() { pre(); while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=cnt&&prime[i]<=n;i++) { for(int j=prime[i];j<=n;j++) dp[j]+=dp[j-prime[i]]; } printf("%d\n",dp[n]); } return 0; }
原文：https://www.cnblogs.com/conprour/p/14825895.html