2022
作者:
不知名的fE
,
2025-02-03 15:31:43
,
所有人可见
,
阅读 1
public class Main {
static final int N = 2500;
//f[i][j][k]表示从前i个数中选k个并且总和为j的方案数
/*
状态转移方程:
f[i][j][k] = f[i - 1][j][k] + f[i - 1][j - primes[i]][k - 1]
初始状态:
f[i][0][0] = 1
目标状态:
f[n][n][10]
采用滚动数组优化空间复杂度防止申请空间超时
*/
static long[][] f = new long[N][11];
static int n = 2022;
public static void main(String[] args) {
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = n; j >= 1; j--) {
for (int k = 1; k <= 10; k++) {
if (j >= i) f[j][k] += f[j - i][k - 1];
}
}
}
System.out.println(f[n][10]);
}
}