题目描述

一个正整数n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对$10^9+7$取模。

数据范围

1≤n≤1000

输入样例:

5

输出样例:

7

完全背包解法 $O(n^3)$

Java 代码

public class Main{
    public static final int N = 1010;
    public static final int M = (int) (1e9 + 7);

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] dp = new int[N][N];
        dp[0][0] = 1;//一个数都不选是一种方案

        for(int i=1; i<=n; i++){
            for(int j=0; j<=n; j++){
                for(int k=0; j - k * i >= 0; k++){
                    dp[i][j] += dp[i - 1][j - k * i];
                    dp[i][j] %= M;
                }
            }
        }

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

完全背包解法 - 优化

f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]
f[i][j-i] = f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]
替换：f[i][j] = f[i-1][j] + f[i][j-1]
优化一维：f[j] = f[j] + f[j-i]

Java 代码

public class Main{
    public static final int N = 1010;
    public static final int M = (int) (1e9 + 7);

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] dp = new int[N];
        dp[0] = 1;//一个数都不选是一种方案

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

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

计数类DP

public class Main{
    public static final int N = 1010;
    public static final int M = (int) (1e9 + 7);

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] dp = new int[N][N];
        dp[0][0] = 1;

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

        int res = 0;
        for(int i=1; i<=n; i++){
            res = (res + dp[n][i]) % M;
        }

        System.out.println(res);
    }
}