SDNU-1029.巧分整数（奇妙的dp）

SDNU-1029.巧分整数

Description
聪明的lg给syc出了一道简单的题目，syc把脑细胞都用光了也不知道该怎么去做，那么请厉害的你来帮助syc做做这道题目。题目的要求就是取一个整数n，这个整数n大于0小于等于200，然后把这个整数n分为k份，并且每一份不能为0，而且任意两种分法不能相同(不考虑顺序)。

例如：n=8,k=3, 下面三种分法被认为是相同的。
2，2，4；  4,2,2；  2,4,2；

问有多少种不同的分法。
Input
n，k (k<=n<=200，1<=k<=6)
Output
一个整数，即不同的分法。
Sample Input
8 3
Sample Output
5
现在发现dp真是太奇妙了，越深入学习，越能感受到其中的乐趣。
思路 ：

dp[i][j]=dp[i-j][1]+dp[i-j][2]+...+dp[i-j][j]//dp[i][j]表示的是将数字i分成j份

如何理解上面的式子呢？
首先，每一份不能为0，这就要保证每一份至少有一个1，所以先把j个1拿出来，剩余的数字为i-j，然后再把i-j分成1…j份，求和加起来就是上面的式子。
上面的式子是不好处理的，这时候我们求dp[i-1][j-1]来看一看：

dp[i-1][j-1]=dp[(i-1)-(j-1)][1]+dp[(i-1)-(j-1)][2]+...+dp[(i-1)(j-1)][j-1]//化简 ↓
dp[i-1][j-1]=dp[i-j][1]+dp[i-j][2]+...+dp[i-j][j-1]//此式子与dp[i][j]只少了dp[i-j][j] ↓
//所以
dp[i][j]=dp[i-1][j-1]+dp[i-j][j]

下面是AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int main()
{
    int n,k;
    cin>>n>>k;
    int f[201][7];
    memset(f,0,sizeof(f));
    f[0][0]=1;//将下面i = 1，j = 1，带入可得此初始条件
    for (int i=1;i<=n;i++)
        for (int j=1;j<=k;j++)
            if (i>=j)//注意判断条件
                f[i][j]=f[i-1][j-1]+f[i-j][j];
    cout<<f[n][k]<<endl;
    return 0;
}