A+B Problem（再升级）题解

解题思路

步骤：
·用标准埃氏筛求出 ≤n 的所有素数
·定义 dp[i] = 凑成数字 i 的方案数
·初始化 dp[0] = 1（空方案）
·对每个素数 p，从小到大更新 dp（完全背包）
·最终输出 dp[n]

AC代码：

#include<bits/stdc++.h>
using namespace std;
bool flag[1005];
long long dp[1005];
void getPrimes(int n){
    memset(flag,true,sizeof(flag));
    flag[0]=flag[1]=false;
    for(int i=2;i<=n;i++){
        if(flag[i]){
            for(int j=i*2;j<=n;j+=i){
                flag[j]=false;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    getPrimes(n);
    dp[0]=1;
    // 完全背包：组合方案（不考虑顺序）
    for(int p=2;p<=n;p++){// 直接遍历，不用存素数容器
        if(!flag[p]){
            continue;
        }
        for(int i=p;i<=n;i++){
            dp[i]+=dp[i-p];
        }
    }

    cout<<dp[n]<<endl;
    return 0;
}