5、计数类DP &整数划分

AcWing 900. 整数划分

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 1010;
    int a[] = new int[N];
    int s[] = new int[N];
    int n;
    int f[][] = new int[N][N];

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

    //f[i][j]表示只从1~i中选，且总和等于j的方案数
    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        f[0][0] = 1;
        //如果写成如下这种，就会把j属于(0,i-1)漏掉
        /**
         for (int i = 1; i <= n; i ++ )
         for (int j = i; j <= n; j ++ ) {
            f[i][j] = (f[i-1][j] + f[i][j - i]) % mod;
         }
         **/
        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]);
    }
}