计数-小球放盒的八类讨论

本文主要是介绍计数-小球放盒的八类讨论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

球和盒子不同是指两两不同，一类球或盒子有且只有一个。不过可以按照类似的思路分类求解，同时，这类问题中的部分亦可以当作背包问题去求解。
在实际做题中，球放盒子没有思路的时候可以从盒子“放”球的角度去理解。

1、球相同，盒相同，可以为空，000

• 等价于整数拆分
• $dp[i][j]$表示将i拆成小于等于j个整数的方案数
• \(dp[i][j]=dp[i][j-1]+dp[i-j][j]\)
• $dp[i-j][i]$中的每一种情况和整数i拆分成j个整数的每一个情况一一对应
• 边界处理，$dp[0][j]$初始化为1，其本身不再具有任何意义，只是作为$i=j$情况的一个踏板。$dp[0][0]$用不着可以不管。$dp[j][0]$为$0$即可。

2、球相同，盒相同，不能为空 001

• 利用$‘1’$的结果
• \(dp[i][j]-dp[i][j-1]\)

3、球不同，盒不同，可以为空 110

• 每个球有$m$中不同选择
• 为$n^m$

4、球不同，盒不同，不能为空 111

• \(dp[n][m]*m!\)
• $dp[n][m]$表示把$n$个不同球放入$m$个相同盒子且不为空(101)的方案数

5、球不同，盒相同，不能为空 101

• $dp[i][j]$表示将前i个球放入j个盒子中不为空的方案数
• 当前第$i$个球要么放到之前的盒子里，要么新开一个盒子
• \(dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1]\)
• i>=j，边界条件，\(dp[1][1]=1\)，然后一切自动化

6、球不同，盒相同，可以为空 100

• 前面的加起来（101）
• \(sigma(dp[n][i])(i<=1<=m)\)

7、球相同，盒不同，不能为空 011

• 隔板法
• \(c[n-1][m-1]\)

8、球相同，盒不同，可以为空 010

• 给每个盒子放上一个球，问题就等价于将n+m个相同的球放到m个不同盒子里
• c[m+n-1][n-1]

这篇关于计数-小球放盒的八类讨论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！