dfs暴搜

import java.util.*;

public class Main {
    static int n, m, ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            ans = 0;
            m = sc.nextInt();
            n = sc.nextInt();

            dfs(0, 0, m);
            System.out.println(ans);
        }
    }

    /**
    * idx :当前的分身编号
    * start : 当前分身的查克拉从几开始
    * remain : 剩余的查克拉
    */
    static void dfs(int idx, int start, int remain) {
        if (idx == n) {
            if (remain == 0) ans++;
            return;
        }

        for (int i = start; i <= remain; i++) {
            dfs(idx + 1, i, remain - i);
        }
    }
}

dp

f[i][j] :将总量为i的查克拉分为j份
状态转移：最小值为0时，有f[i][j - 1]份
不是0时，将每一份减去1的方案数和该方案数相同：f[i - j][j]
累加

初始化f[0][0] = 1;总量为0时分为0份的方案数为1
f[0][1] = … = 0;总量为0时分为i份的方案数为1
f[1][0] = … = 0; …

查克拉从0开始枚举到m

import java.util.*;

public class Main {
    static int[][] f = new int[11][11];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t -- > 0) {

            int m = sc.nextInt(), n = sc.nextInt();

            f[0][0] = 1;
            for (int i = 0; i <= m; i++) 
                for (int j = 1; j <= n; j++) {
                    f[i][j] = f[i][j - 1];
                    if (i >= j)
                        f[i][j] += f[i - j][j];
                }
            System.out.println(f[m][n]);
        }
    }
}