题目可理解成 给一个数n，再给无限个 1，无限个 2，...无限个 n 求用给你的这些数加和为 n 有多少种方法。
可转换为数学式来表示
(1+x+x^2+x^3+x^4+...)(1+x^2+x^4+...)(1+x^3+x^6+..)...
其中(1+x+x^2+x^3+x^4+...)表示1不取 或取1次 或取2次 或取3次...
(1+x^2+x^4+...)
表示2不取 或取1次 或取2次 或取3次...
(1+x^3+x^6+..)
表示3不取 或取1次 或取2次 或取3次...
将全部式子整合后 x^n前面的系数即为加和为n的方法总数。
那么用代码表示 即要整合这些式子
按部来(1+x+x^2+x^3+x^4+...)(1+x^2+x^4+...)先用数组ans[]储存(1+x+x^2+x^3+x^4+...)的系数，都为1；还要数组temp[]存储(1+x+x^2+x^3+x^4+...)(1+x^2+x^4+...)计算之后整合好了的系数，先初始化为0；
每次(1+x+x^2+x^3+x^4+...)中第j个数与(1+x^2+x^4+...)中系数为k的数相乘，新式子的指数为j+k的数的系数即temp[j+k]+=ans[j]再把temp的值给ans，temp的值归0，计算（新式子)(1+x^3+x^6+..)
依此类推。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int ans[] = new int[121];
int temp[] = new int[121];
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
for(int i=0; i<=n; i++) {
ans[i] = 1; //储存最前面式子的系数
temp[i] = 0; //储存整合后最前面式子和下一个式子的系数
}
for(int i=2; i<=n; i++) { //整合前俩个式子，i表示第几个式子
for(int j=0; j<=n; j++) //j表示最前面式子的第j项
for(int k=0; k+j<=n; k+=i) //k表示下一个式子的每一项指数
temp[k+j] += ans[j]; //计算新生成的指数为k+i的项的系数
for(int j=0; j<=n; j++) { //把新式子的系数交接
ans[j] = temp[j];
temp[j] = 0;
}
}
System.out.println(ans[n]);//输出指数为n的项的系数
}
}
}
