暴力

//鸣人的影分身

//暴力做法：依次枚举每一个影分身分配的能量是多少，然后不断向下递归

#include<iostream>
#include<cstdio>

using namespace std;
int res;
int m,n,t;

void dfs(int u,int alloc, int chakla)
{
    // u 当前枚举到第几个分身 alloc 上一个影分身分配多少查克拉，chakla 剩余多少查克拉

    //定义边界条件
    if(u==n&&chakla==0)
    {
        //凑够n个影分身并且剩余查克拉能量为0 则返回
        res++;
        return ;
    }
    if(u>n) return ;
    //枚举每个分身的能量
    for(int i=alloc;i<=chakla;i++)
    {
        dfs(u+1,i,chakla-i);
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        res=0;
        scanf("%d%d",&m,&n);
        dfs(0,0,m);
        cout<<res<<endl;
    }
    return 0;
}

dp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int res;
int m,n,t;
const int N=12;
int f[N][N];

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        //查克拉能量为m，总分身个数为n 
        memset(f,0,sizeof(f));
        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];
                }
            }
        }
        cout<<f[m][n]<<endl;
    }
    return 0;
}