DFS+DP两种方法

· · 题解

本蒟蒻的第一篇题解，希望大家能看懂

一 DFS解法

我最开始的想法就是写一个DFS，比较简单。

last代表这次划分的数，循环时从last开始，就可以避免重复了。

ni代表还需要分的数

ki代表还需要分的份数

每次分到ni/ki就够了，否则后面就不够分了

#include<iostream>
using namespace std;
int v[201][7]={},n,k;
int dp(int last,int ni,int ki)
{
    if(ki==1)       return 1;
    int s=0;
    for(int i=last;i<=ni/ki;i++)
            s+=dp(i,ni-i,ki-1);
    return s;
}
int main()
{
    cin>>n>>k;
    cout<<dp(1,n,k);
}

二、DP解法

这个是看了其他大佬的解法后写出来的，本蒟蒻之前没有想到，看到其他大佬的题解比较难理解（可能是本蒟蒻太弱了），所以我也写上我的理解。

（引用一下另一个大佬的题解）

“solution【i】【j】代表在数的和为i的情况下分为j组共有的情况数。由于无论在数的和为几时，把它们分成0组都是0种情况，分成一组都是一种情况，所以j=0时全部要初始化为0，j=1时全部要初始化为1。同时，无论共分为几组，数的和为0和1是0种情况（i=j=1除外）所以i=0或i=1时j从2开始全部初始化为0。对于剩下的任意一个solution【i】【j】（i>=j)，都可以用如下方式求得：solution【i】【j】=第一个数为1的所有情况+第一个数不为1的所有情况。”

第一个数为1时，1占用了1个位置并且划分为1个区域，因此，第一个数为1的所有情况=solution【i-1】【j-1】。

第一个数不为1时，可以视为先在位置上都加上一个1，因为分出1后剩下 i-j可分的1，还需分j份，所以占有了总数j个，位置仍然是j个（solution【i-j】【j】）。

综上所述，solution【i】【j】=solution【i-1】【j-1】+solution【i-j】【j】。

#include<iostream>
using namespace std;
int main()
{
    int n,k,solution[201][7]={};
    cin>>n>>k;
    for(int i=0;i<n;i++)
            solution[i][0]=0,solution[i][1]=1;
    for(int i=2;i<k;i++)
            solution[0][k]=0,solution[1][k]=0;
    for(int i=1;i<=n;i++)
            for(int j=1;j<=k;j++)
                    if(j>i)      solution[i][j]=0;
                    else         solution[i][j]=solution[i-1][j-1]+solution[i-j][j];
    cout<<solution[n][k];
}