【蓝桥杯】质数拆分

将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？
注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017 + 2 = 2019视为同一种方法。

隐藏条件(坑点)：当一个数本身就是质数时，算一种方法问题转化为：输入一个数 n n n，求出 [ 2 , n ] [2,n] [2,n] 之间的所有质数，然后在这些质数中任选 k k k 个质数，使这 k k k 个质数的和为 n n n，求不同的选取方法数如果真的要与“组合数”扯上关系的话，那么复杂度就太高了，为了尽量降低复杂度，用动态规划比较好

动态规划1：

建一个二维DP数组 d p [ ] [ ] dp[][] dp[][] ，注意方法数可能很大，所以这个数组应该用 l o n g   l o n g long long long long 类型该数组的一个维度为 [ 2 , n ] [2,n] [2,n] 的质数编号，一个维度为 [ 0 , n ] [0,n] [0,n] 下标DP数组 d p [ i ] [ j ] dp[i][j] dp[i][j]的含义为在前 i i i个质数中，能组成 j j j的最大方法数 d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1

优化：

将二维数组压缩为一维数组 d p [ ] dp[] dp[] d p [ 0 ] = 1 dp[0]=1 dp[0]=1 代码如下

#include 
#include 
#define ll long long
using namespace std;

vector prime_num;  //质数数组
int t;                  //质数数组的大小
vector> dp;  // DP数组
int N;                  //输入的N

//朴素的判断一个数是不是质数的方法
bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

//准备[2,n]之间的质数
void init() {
    scanf("%d", &N);
    prime_num.push_back(0);  //质数下标从1开始
    for (int i = 2; i < N; i++) {
        if (is_prime(i)) {
            prime_num.push_back(i);
        }
    }
    t = (int)prime_num.size();
    dp.resize(t);
    for (int i = 0; i < t; i++) {
        dp[i].resize(N + 1);
    }
}

void solve() {
    dp[0][0] = 1;
    for (int i = 1; i < t; i++) {
        for (int j = 0; j <= N; j++) {
            //先假设选这个数之后不能组成j，则“继承”上一个的方法数
            dp[i][j] = dp[i - 1][j];
            //如果判断发现能组成，则加上之前的方法数
            if (j >= prime_num[i]) {
                dp[i][j] += dp[i - 1][j - prime_num[i]];
            }
        }
    }
    printf("%lldn", dp[t - 1][N]);

    
    // dp[0] = 1;
    // for (int i = 1; i < t; i++) {
    //     for (int j = N; j >= prime_num[i]; j--) {
    //         dp[j] += dp[j - prime_num[i]];
    //     }
    // }
    // printf("%lldn", dp[N]);
}

int main(void) {
    init();
    solve();
    return 0;
}