题目描述

数字n，可分解成其他正整数的有多少个不同方案数（不区分顺序）

朴素解法

动态规划 完全背包思想
状态表示：f[i, j] 表示从 1 到 i 组合成 j 的方案数
状态属性：数量
状态计算：f[i, j] = sum(f[i-1, j-k*i]) 其中 k = [0, j/i]

import java.util.*;

public class Main {

    private static int N = 1010;
    private static int[][] f = new int[N][N];
    private static int mod = (int) 1e9+7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 初始化
        for (int i=0; i<=n; i++) f[i][0] = 1;

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

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

二维数组优化

f[i, j] = sum(f[i-1,j], f[i-1,j-i], f[i-1,j-2*i]…)
f[i, j-i] = sum(f[i-1, j-i], f[i, j-2*i]…)
对比：f[i, j] = sum(f[i-1, j], f[i, j-1])

import java.util.*;

public class Main {

    private static int N = 1010;
    private static int[][] f = new int[N][N];
    private static int mod = (int) 1e9+7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 初始化
        for (int i=0; i<=n; i++) f[i][0] = 1;
        // f[i, j] = sum(f[i-1,j], f[i-1,j-i], f[i-1,j-2*i]...)
        // f[i, j-i] = sum(f[i-1, j-i], f[i, j-2*i]...)

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

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

一维数组优化

import java.util.*;

public class Main {

    private static int N = 1010;
    private static int[] f = new int[N];
    private static int mod = (int) 1e9+7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 初始化
        f[0] = 1;
        // f[i, j] = sum(f[i-1,j], f[i-1,j-i], f[i-1,j-2*i]...)
        // f[i, j-i] = sum(f[i-1, j-i], f[i, j-2*i]...)

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

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