朴素版本

import java.util.*;

class Main {
    static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] f = new int[n+1][n+1];
        //初始化
        //用1表示其他数都是只有1种表示方法
        Arrays.fill(f[1], 1);
        //注意f[i][0]要设为0，意义是计算f[i+1][j]时，j-k*i==0即j能表示成k个i，是一种方案
        for (int i = 1; i <= n; i++) f[i][0] = 1;

        //第一行已初始化，从第二行开始枚举即可
        for (int i = 2; i <= n; i++)
            for (int j = 1; j <=n; j++) {
                for (int k = 0; k*i <= j; k++)
                    f[i][j] = (f[i][j] + f[i - 1][j - k*i]) % mod;
                //System.out.println(String.format("f[%d][%d] : %d",i,j,f[i][j]));
            } 

        System.out.println(f[n][n]);
    }
}

时间优化

//通过化简状态方程进行优化

import java.util.*;

class Main {
    static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] f = new int[n+1][n+1];
        //初始化
        //用1表示其他数都是只有1种表示方法
        Arrays.fill(f[1], 1);
        //注意f[i][0]要设为0，意义是计算f[i+1][j]时，j-k*i==0即j能表示成k个i，是一种方案
        for (int i = 1; i <= n; i++) f[i][0] = 1;

        //第一行已初始化，从第二行开始枚举即可
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <=n; j++) {
                //优化后的方程中j - i可能为负，需判断
                if (j - i < 0) f[i][j] = f[i - 1][j];
                else f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
                //System.out.println(String.format("f[%d][%d] : %d",i,j,f[i][j]));
            } 

        System.out.println(f[n][n]);
    }
}

进一步空间优化

import java.util.*;

class Main {
    static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] f = new int[n+1];
        //初始化
        f[0] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = i; j <=n; j++) {
                f[j] = (f[j] + f[j - i]) % mod;
            } 

        System.out.println(f[n]);
    }
}