[概率练习]n个小球放入m个盒子

球可以相同也可以不同，盒子可以一样也可以不一样，盒子可以空也可以不能空，那么一共就有2*2*2=8种

n个小球放入m个盒子

1.球同，盒不同，不能空

用插板法

一共有n-1个空隙(总共n+1个空隙，不能空要去掉头尾=n-1) ，要插m-1个板，

答案就是

上图就是7个小球3个盒子的一种情况

2.球同，盒不同，能空

如果给每个盒子一个球，就可以把问题转化为不能空的情况了,就相当于n+m个小球放入m个盒子且不能空

答案就是

3.球不同，盒同，不能空

这就是个dp问题了

dp[n][m]代表n个小球放入m个不同的盒子且不能空的方法

当i>=0时,dp[i][i]=1(i个小球放入i个盒子，就只能1个盒子放1个)

当i>0时,dp[i][0]=0(都没有盒子了，肯定无解)

dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1]