1303：鸣人的影分身

【算法分析】
? ? ? ?该问题可以等价描述为：将数字m写成n个数字加和的形式，每个数字大于等于0，分成的多个数字没有先后顺序，求数字相加的方案数。以下以数字加和为背景进行论述，用动态规划的分析方法分析该问题。

1. 状态定义
状态定义：
dp[i][j]：将数字i划分为j个数字加和（数字可以为0）的方案数。
初始状态：
将数字i划分为1个数字的加和，方案为1。dp[i][1] = 1
将数字0划分为j个数字的加和，就是j个0相加，方案为1。dp[0][j] = 1

2. 状态转移方程
集合：将数字i划分为j个数字相加的方案
分割集合：以划分后的多个相加的数字中是否存在数字0进行划分。

? ? ? ? 如果存在数字0，那么将数字i划分为j个数字相加的方案数，其中一个数字为0，就相当于将数字i划分为j-1个数字相加的方案数：dp[i][j-1]。
? ? ? ? 如果划分后的j个数字中不存在0，那么可以先为每个数字分配1个1，共分配掉大小为j的数值，还剩下数值i-j。接下来就是将数值i-j划分为j个数字，划分出的数字可以为0，每个数字加上刚才分配的1，就是将数值i划分为j个数字后的每个数字。这样做的方案数为：dp[i-j][j]
? ? ? ? 如果j > i ，将数字i划分为j个数，一定存在数字0，所以只能选择这一种情况：dp[i][j] = dp[i][j-1]。否则 以上两种情况加和，为将数字i划分为j个数字相加的方案数：dp[i][j] = dp[i][j-1]+dp[i-j][j]。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
#define N 15
#define INF 0x3f3f3f3f
int t, m, n, dp[N][N];//dp[i][j]:将数字i划分为j个数字加和（数字可以为0）的方案数。
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> m >> n;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i <= m; ++i)
            dp[i][1] = 1;
        for(int j = 1; j <= n; ++j)
            dp[0][j] = 1;
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
            {
                if(i < j)
                    dp[i][j] = dp[i][j-1];
                else
                    dp[i][j] = dp[i][j-1]+dp[i-j][j];
            }
        cout << dp[m][n] << endl;
    }
    return 0;
}