问题描述

2019可以被分解成若干个两两不同的素数，请问不同的分解方案有多少种？
注意：分解方案不考虑顺序，如 2 + 2017 = 2019 和 2017 + 2 = 2019 属于同一种方案。

问题分析

首先需要找到2019以内的所有质数，这里推荐使用埃式塞法。

因为这里是拆成了若干个不同的素数，得考虑不同的问题。
简化分析，10的分解方案。

我们可以对素数进行遍历看看。
2的时候可以拆成2+8（然后在对3、5、7）
对8在进行这样拆
2的时候可以拆成2+6....

可以看到似乎是得之前前面的最优解，这里就很容易的想到动态规划了。

dp[i][j] 表示：对前i个质数中选取刚好是j

• 如果不选第i个数，就是dp[i−1][j]dp[i-1][j]dp[i−1][j]
• 如果选第i个数，就是dp[i−1][j−primes(i)]dp[i-1][j-primes(i)]dp[i−1][j−primes(i)]
• dp[i][j]=dp[i−1][j]+dp[i−1][j−primes(i)]dp[i][j]=dp[i-1][j]+dp[i-1][j-primes(i)]dp[i][j]=dp[i−1][j]+dp[i−1][j−primes(i)]

好了状态方程有了。进行初始化。

• dp[0][0]=1dp[0][0]=1dp[0][0]=1

进行遍历就可以了。

优化：我们可以压缩成一维数组
dp[i]表示i数字的最优解。

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = 2019;boolean[] f = new boolean[n + 1];ArrayList primes = new ArrayList<>();for (int i = 2; i <= n; i++) {if (!f[i]) {primes.add(i);for (int j = i + i; j <= n; j += i) {f[j] = true;}}}long[] dp = new long[n+1];dp[0] = 1;for(int i = 0; i < primes.size(); i++){int a = primes.get(i);for(int j = n; j >= a; j--){dp[j] += dp[j - a];}}System.out.println(dp[n]);}
}