题目描述

完全背包问题
每一个数字都可以被使用无限次，同时题目保证忽略顺序

package dp;

import java.util.Scanner;

public class 自然数拆分 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    Scanner scanner=new Scanner(System.in);
   long mod=Long.parseLong("2147483648");
    int n=scanner.nextInt();
   long f[][]=new long [n+1][1+n];
    f[0][0]=1;
    for(int i=1;i<=n-1;i++){
        for(int j=0;j<=n;j++){
            f[i][j]=(int) (f[i-1][j]%mod);
            if(j>=i){
                f[i][j]=(int) ((f[i][j]+f[i][j-i])%mod);
            }
        }
    }
    System.out.println(f[n-1][n]);
    }

}