完全背包

package dp;

import java.util.Scanner;

public class 整数划分 {

    /**
     * @param args
     */
    static int mod=(int) (1e9+7);


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        int f[][]=new int [n+1][n+1];
        //表示的含义是从n个物品中选，体积是n的物品

        f[0][0]=1;
        //其余状态默认是0，包括不合法的状态

        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++){
                f[i][j]=f[i-1][j];
                if(j>=i){
                    f[i][j]=(f[i][j]+f[i][j-i])%mod;
                }
            }
        }
        System.out.println(f[n][n]);


    }
}

其他做法

package dp;

import java.util.Scanner;

public class 整数划分1 {

    static int mod=(int) (1e9+7);


    public static void main(String[] args) {

        Scanner scanner =new Scanner(System.in);
        int n=scanner.nextInt();
        int f[][]=new int [n+1][n+1];
        //f[i][j]表示的是总和是i，可以表示成j个数字相加的形式
        f[0][0]=1;
        //也可以I从2开始，f[1][1]=1
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=f[i-1][j-1];
                if(i>j) f[i][j]=(f[i][j]+f[i-j][j])%mod;
            }
        }
        int res=0;
        for(int i=1;i<=n;i++){
            res=(f[n][i]+res)%mod;;
        }

        System.out.println(res);




    }

}