[Acwing蓝桥杯DP] 1050. 鸣人的影分身

题目链接：1050. 鸣人的影分身 - AcWing题库

题目大意：t组数据，每组数据有个正整数m分成n个非负数的方案

方案中不考虑顺序，例(2,2,3)">(2,2,3) 和 (2,3,2)">(2,3,2) 被视为同一种方案

(2,2,3)">(2,3,2)">数据范围：0<= t <=20

(2,2,3)">(2,3,2)">                  1<=n,m<=10

分析：这个题数据范围比较小，虽然可以暴力过，但是容易爆，也可以打表

正确做法是DP，时间复杂度是O(n^2)；

ps:这个题中不考虑顺序，如果考虑顺序的化就是插板

闫氏DP分析法:

集合：f [ i ][ j ] :表示总和为 i ，方案数为 j 。

属性:  方案数

状态转移：

方式划分    （1） 整个序列的最小值为 0

                  （2）整个序列的最小值大于0

转移：f [ i ][ j ]=f [ i ][ j -1 ]+f [ i - j  ( i>=j ) ][ j ]

初始化：f [ 0 ][ 0 ] = 1;// 表示没有数的时候 总和为0 方案成立

代码：

#include 
using namespace std;
const int N=15;
int f[N][N];
int n,m;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(f,0,sizeof f);
        cin>>m>>n;
        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<endl;
    }
    return 0;
}

end!!!