1029.巧分整数

题意：

将n分成k个数，每个数不能为0，分法不能重复（不考虑顺序）

思路：

神奇的dp！

dp[i] [j] = dp[i - j] [j - 1] + dp[i - j] [j] (dp[i] [j]指将i分成j份）

因为每个数不能为0，所以对于数i，先减去j，得到能支配的数，在将这些数进行分配。所以dp[i] [j] = dp[i - j] [1] + dp[i - j] [2] + …… + dp[i - j] [j]。都是这样不太好处理，所以进行一次简化。

dp[i - 1] [j - 1] = d p[i - 1 - (j - 1)] [1] + ……dp[i - 1 - (j - 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].

#include<bits/stdc++.h>
using  namespace std;
#define MAX 1000+5
typedef  long long ll ;
int tr[MAX][10], n, q;
int main()
{
    cin>>n>>q;
    memset(tr, 0, sizeof(tr));
    tr[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= q; j++)
        {
            if(i >= j)
                tr[i][j] = tr[i - 1][j - 1] + tr[i - j][j];
        }
    }
    cout<<tr[n][q]<<endl;
    return 0;
}