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