AcWing 1050. 鳴人的影分身

• 2022 年 4 月 2 日
• 筆記
• DP, 刷題

題目鏈接

題目描述：
在火影忍者的世界裡，令敵人捉摸不透是非常關鍵的。
我們的主角漩渦鳴人所擁有的一個招數——多重影分身之術——就是一個很好的例子。
影分身是由鳴人身體的查克拉能量製造的，使用的查克拉越多，製造出的影分身越強。
針對不同的作戰情況，鳴人可以選擇製造出各種強度的影分身，有的用來佯攻，有的用來發起致命一擊。
那麼問題來了，假設鳴人的查克拉能量為 M，他影分身的個數最多為 N，那麼製造影分身時有多少種不同的分配方法？

題目大意：給定一個數M，求將其拆分為不少於N個數的方案數。不考慮順序，即（2，2，3）和（2，3，2）是同一種方案。
解決方法：DP
集合：所有總和是i，且分成j個數的和的方案（j個數中可以有0）
集合劃分：

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 11;

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n, m;
        scanf("%d%d", &m, &n);

        int f[N][N] = {0};
        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];
            }

        printf("%d\n", f[m][n]);
    }

    return 0;
}