题目描述

在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。 影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。 针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。 那么问题来了，假设鸣人的查克拉能量为M，他影分身的个数为N，那么制造影分身时有多少种（用K表示）不同的分配方法？（影分身可以被分配到0点查克拉能量）.答案不考虑顺序。

输入

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1 <= M，N <= 10。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入 

1
7 3

样例输出 

8

 

这道题是最简单的一道题，甚至用递归就能解决，dp？也行！不过我我们还是要梳理一下思路：

 

递归法：

 

F(M,N) 为M查克拉分给N个分身的分配方案数，首先发现 M=1||M=0||N=1 -> F(M,N)=1M<=N的情况，那就算M个查克拉全部分开分配也只能分给M个分身,所以至少有(M-N)个分身没分到，它们的地位相同，所以此时F(M,N)=F(M,M)。我们令其中一个分身分不到查克拉，就是说M单位查克拉分给N-1个分身，这说明F(M,N)可以由F(M,N-1)。F(M,N)=F(M-N,N)+F(M,N-1) M>=N。

接下来就So Easy了！

#include <bits/stdc++.h>
using namespace std;

int f(int m, int n)
{
    if (m == 0 || n == 1)
        return 1;
    if (m < n)
        return f(m, m);
    return f(m, n - 1) + f(m - n, n);
}

int main()
{
    int a;
    cin >> a;
    while (a--) {
        int m, n;
        cin >> m >> n;
        cout << f(m, n)<<endl;
    }
    return 0;
}

 

 

DP法：

d[i][j]表示把 i 查克拉分给 j 个分身的方案数，当然 j 必须小于等于 i ，因为此时每个分身正好每人一查克拉，不能再少了。状态转移方程就是：d[i][j]=d[i-j][j]+d[i-1][j-1]。

注意：这里需要考虑两种情况，两种情况是不同的dp方程！

#include <bits/stdc++.h>
using namespace std;
int f[101][101];

int main()
{
    int a;
    cin >> a;
    while (a--) {
        int n, m;
        cin >> m >> n;
        int f[11][11] = {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];
            }

        cout << f[m][n]<<endl;
    }

    return 0;
}