本文共 662 字，大约阅读时间需要 2 分钟。

写了几个题发现整数划分是一类题，而不是一道题。

具体题型：

1、n相同元素放入m个相同的盘子 盘子允许为空  例题：

设dp[i][j]为  j 个元素放入i个盘子

转移方程：

dp[i][j]+=dp[i-1][j]  新添加一个盘子，盘子为空

dp[i][j]+=dp[i][j-i] i个盘子 各取出一个 

 

2、n个相同的元素放入m个不同的盘子，盘子允许为空 

隔板法 

新加m个元素使得盘子不能为空

演变为n+m个元素分成m个不同的盘子  盘子不允许为空

答案：C(n+m,m-1)

 

3、n个相同的元素放入m个相同的盘子，盘子不允许为空

设dp[i][j]为  j 个元素放入i个盘子

转移方程：

dp[i][j]+=dp[i-1][j-1]  新添加一个盘子，盘子放一个

dp[i][j]+=dp[i][j-i] i个盘子 各取出一个 

 

4、n个不同的元素放入m个相同的盘子，盘子不允许为空 组内无序

斯特林数

设dp[i][j]为  j 个元素放入i个盘子 

转移方程：

dp[i][j]+=dp[i-1][j-1]  不允许为空

dp[i][j]+=dp[i][j-1]*i   新添加一个元素，由于元素是不同的，所以可以放i个盘子任何一个都可以。

这个可以用斯特林数求法优化：

不过这张图分析的怎么柑橘允许有空的盘子呢？

献上wiki百科的知识点，是不允许为空的：

 

 

5、n个不同的元素放入m个不同的盘子，盘子不允许为空 组内无序

还是斯特林数，上面那个公式除了一个m 的阶乘就是使得m是相同的，这题就不要除m的阶乘就好了

6....待添加

转载地址：https://ccsudeer.blog.csdn.net/article/details/106282118 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！