AcWing 279. 【Java】自然数拆分
原题链接
简单
作者:
tt2767
,
2020-01-13 22:32:05
,
所有人可见
,
阅读 802
/*
1. 状态定义:f[j] 表示和为j拆分数
2. 状态计算: f[j] += f[j-a[i]]
3. f[~] = 0 , f[0] = 1;
4. 注意下 mod 值比int大, java中常量要在后面加L
5. 必须拆为2个数,所以没有0和n
*/
import java.util.*;
public class Main{
void run(){
int n = jin.nextInt();
f[0] = 1;
for (int i = 1 ; i< n ; i++){
for (int j = i ; j<= n ; j++){
f[j] = (f[j] % mod + f[j-i] % mod ) % mod;
}
}
System.out.println(f[n]);
}
long mod = 2147483648L;
long[] f = new long[4002];
Scanner jin = new Scanner(System.in);
public static void main(String[] args) {new Main().run();}
}