划分数问题

https://blog.csdn.net/csyifanZhang/article/details/105652758
↑为了更好的阅读体验

这道题是一个模板题，所以先上原模板：

这样的划分被称作的划分数，特别地，时称作 的划分数、DP不仅对于求解最优问题有效,对于各种排列组合的个数、概率或者期望之类的计算同样很有用。在此，我们定义如下。

根据这一定义可以得到怎样的递推关系呢？将个划分成个的话，可以先取出个然后将剩下的个分成份，这时大家是不是认为也许就可以得到下面的递推式了？
$$

但很不幸的是，这个递推是不正确的。用这个办法的话，例如1+1+2和1+2+1的划分就被当成是不同的划分来计数了。为了不重复计数，我们需要寻找别的递推关系。考虑的划分，

• 如果有任意，那么也就是的划分此时这两个组合数是一样的，因为前者也只是给后者每个位置+1而已。
• 如果存在，那么就对应了的划分。

而对于的而言，这两种可能性显然都可以在他的排列种发生，而如果，那么只有第二种情况会发生。因此我们有

if(j>=i)dp[i][j]=(dp[i-1][j]+dp[i][j-i])\%M

else ~dp[i][j]=dp[i-1][j]

例题：牛客网-放苹果

题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入描述:

每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

输出描述:

对输入的每组数据M和N，用一行输出相应的K。

#define ll int
#define vec vector<ll>
#define MAX 15
#define inf 0x3fffffff

ll dp[MAX][MAX];

int main() {
    ll M, N;
    while (cin >> M >> N) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            //j从零开始，也就是每行的第一列都是1 dp[i][0]=1 因为盘子可以为空
            for (int j = 0; j <= M; j++) {
                if (j >= i)dp[i][j] = dp[i - 1][j] + dp[i][j - i];
                else dp[i][j] = dp[i - 1][j];
            }
        }
        cout << dp[N][M] << endl;
    }
}