题目：给出一个整数n,求解该整数n有多少种由2的幂次之和组成的方案. 1) 1+1+1+1+1+1+1 2) 1+1+1+1+1+2 3) 1+1+1+2+2 4) 1+1+1+4 5) 1+2+2+2 6) 1+2+4 思路：1.n为奇数时，n的种类数就等于n-1种类数 arr[n]=arr[n-1] 2.n为偶数时，如果加数里含1，则至少有两个1，也就是在n-2的分解因式后+1+1，总类数为arr[n-2]。如果加数里没有1，n/2的因式的每个因子都要乘以2，总类数为arr[n/2]；
import java.util.Scanner; public class Sumset { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] arr=new int[n+1]; arr[0]=1; arr[1]=1; for (int i = 2; i <arr.length; i++) { if (i%2>0) { arr[i]=arr[i-1]; }else { arr[i]=arr[i-2]+arr[i/2]; arr[i]%=1000000000; } } System.out.println(arr[n]); // TODO Auto-generated method stub } }