整数划分

记忆化

DFS加记忆化，由于相同划分的不同顺序算作一个序列，因此要多加一个维度，保证数字选择是不递减的，以避免重复选择的情况。

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(new Main().helper(n,1, new Integer[n+1][n+1]));
    }

    // Memo[i][j]表示从数字i开始选择，总和为j的方案总数
    public int helper(int n, int j, Integer[][] Memo){
        int mod = (int)1e9+7;
        if(Memo[n][j] != null)
            return Memo[n][j];
        if(n == 0)
            return 1;

        int count = 0;
        for(int i = j; i <= n; i++){
            count = (count + helper(n-i, i, Memo)) % mod;
        }

        return Memo[n][j] = count;
    }
}

动态规划

类比完全背包

可以将n看做是一个容量为n的背包，从1-n中选择几个数，使得恰好装满这个背包的方案数。

状态表示

• 集合：$(i,j)$表示从1-i中选择几个数恰好容量为j的所有方案的集合

• 属性：集合中元素(方案)的数量

状态计算/集合划分

• 选0个i
• 选1个i
• …
• 选k个i

两个方程

$$f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-2*i)+…+f(i-1,j-k*i)$$

$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f(i,j-i)=f(i-1,j-i)+f(i-1,j-2*i)+…+f(i-1,j-k*i)$$

化简得

$$f(i,j)=f(i-1,j)+f(i,j-i)$$

代码：

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = (int)1e9+7;
        int[] dp = new int[n+1];
        dp[0] = 1;

        // 先枚举物品，在枚举容量
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                dp[j] = (dp[j] + dp[j-i]) % mod;
            }
        }

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

另一种思路

状态表示

• 集合：$(i,j)$表示使用j个数能够凑成总和为i的方案的集合
• 属性：$f(i,j)$表示这些方案的数量

状态计算/集合划分

• 使用j个数能够凑成i，这j个数中最小值为1的集合，去掉一个1，则状态变为：$f(i,j)=f(i-1,j-1)$
• 使用j个数能够凑成i，这j个数中最小值不为1的集合，将这j个数都减去一个1，则状态变为：$f(i,j)=f(i-j,j)$，此时状态表示为j个数能够凑成i-j的所有方案的数量。

将两个数量相加

$$f(i,j)=f(i-1,j-1)+f(i-j,j)$$

代码

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = (int)1e9+7;
        int[][] dp = new int[n+1][n+1];
        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]) % mod;
            }
        }

        // 最后还要统计所有得到n的方案数
        int res = 0;
        for(int i = 1; i <= n; i++)
            res = (res + dp[n][i]) % mod;
        System.out.println(res);
    }
}