经典DP/DFS【数的划分】

给出一个整数n和k，问有多少种方式将n分成k份
首先看数据范围，很明显可以直接爆搜得到答案，这里就不过多讨论

void dfs(int cnt,int pre,int res) //cnt划分层数，pre前一个数，res记录剩下的待划分的数
{
    if(cnt==k-1)
    {
        if(res>=pre) num++;
        return;
    }
    for(int i=pre;i<=res;i++) dfs(cnt+1,i,res-i);
}

int main()
{
    n=read(),k=read();
    dfs(0,1,n);
    printf("%d\n",num);
}

然后考虑dp的做法。
对于将一个数字分成k份，我们可以类比为有n个球，我们要将这n个球放入k个盒子中
我们用dp[i][j]表示将i个球放入j个盒子中有多少种放法
易知，i==j时，dp[i][j]=1;
i<=j,时，dp[i][j]=0;
现在考虑 i>j 的情况
由于我们知道，当i==j时，即将一个小球放入一个盒子，cnt=1;
所以我们假设所有放法分为俩种
1.至少有一个盒子放一个小球
2.所有盒子都放了俩个小球及以上
对于第一种情况，我们可以得知，dp[i][j]=dp[i-1][j-1] //因为少了一个盒子和一个球对整体的方案数不发生改变
对于第二种情况，我们可以看作是(i-j)个球放入了j个盒子之中，比如往3个盒子里面放7个球，可以有2,2,3的方案，这也等同于往3个盒子里面放4个球，有1,1,2的方案，这样我们通过状态转移又转移到了第一种情况
综上所述，我们可以得出状态转移方程
dp[i][j]=dp[i-1][j-1]+dp[i-j][j]//第一种情况加上第二种情况

#include <iostream>
#include <cstdio>
#include <algorithm>
int f[205][10];    
using namespace std; 
int main() 
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        f[i][1]=1;    //将i划分成1份肯定只有一种 
        f[i][0]=0;    //将i划分成0份肯定不存在 
    }
    for(int i=2;i<=k;i++)
    {
        f[1][i]=0;    //将1划分成i份(i>1)肯定不存在 
        f[0][i]=0;    //将0划分成i份(i>1)肯定不存在
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=k;j++)
        {
            if(i>j)
                f[i][j]=f[i-1][j-1]+f[i-j][j];//至少有一个盒子为装了一个小球的情况加上没有一个盒子只有一个小球的情况 
            else    
                f[i][j]=f[i-1][j-1];//j>=i,答案其实一定为1 
        }
    }
    printf("%d",f[n][k]);
    return 0;
}