划分数问题_牛客博客

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

这道题是一个模板题，所以先上原模板：
在这里插入图片描述
这样的划分被称作 $n$ 的 $m$ 划分数，特别地， $m=n$ 时称作 $n$ 的划分数、DP不仅对于求解最优问题有效,对于各种排列组合的个数、概率或者期望之类的计算同样很有用。在此，我们定义如下。

$dp[i][j]:j的i划分总数$

根据这一定义可以得到怎样的递推关系呢？将 $j$ 个划分成 $i$ 个的话，可以先取出 $k$ 个然后将剩下的 $j-k$ 个分成 $i-1$ 份，这时大家是不是认为也许就可以得到下面的递推式了？
$ $dp[i][j]=\sum_{k=0}^j{dp[i-1][j-k]}$ $

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

如果有任意 $a_i>0$ ，那么 $\{a_1-1,a_2-1,...,a_m-1\}$ 也就是 $n-m$ 的 $m$ 划分此时这两个组合数是一样的，因为前者也只是给后者每个位置+1而已。
如果存在 $a_i=0$ ，那么就对应了 $n$ 的 $m-1$ 划分。

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

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;
    }
}