数的划分 (Java代码）

import java.util.Scanner;

public class Main {
	static int nums=0;
	public static void main(String[] args) {
		//最后面几个数可能会超时，打表存储起来。
			Scanner sc=new Scanner(System.in);
			int[]a=new int[]{56634173,64112359,72533807,82010177,92669720,
					104651419,118114304,133230930,150198136,169229875,190569292};
			int n=sc.nextInt();
			if(n>=90){ System.out.println(a[n-90]);}
			else{
				dfs(1,n);
				System.out.print(nums);
			 }
   }
	static void dfs(int index,int n){
		for (int i = index; i <=n; i++) {
			if(n-i<0) break;
			if(n-i==0){nums++;  break;}
				dfs(i,n-i);
		}
	}
}