匿名1587
(匿名1587)
1
10月底onsite，国人老哥最后还有15分钟左右又问了我道dp，n个苹果放进m个箱子，箱子是identical的，问有多少种放法.
当时第一反应dp，可是写出来的公式都被指出没办法去除重复的方法，后来国人老哥提示分两种state，讨论得出来一种state是每个箱子都起码有一个苹果，还有一种state是起码有一个箱子没有苹果，当时他这个想法是得到他肯定的，他让我具体写出state公式，最后时间不多了也没写出来。
鄙人水平不够，感觉这题还是挺难的，回来稍微查了查应该是离散数学里面的题目，没学过，不知道是不是直接有数学公式能解决。
mine
2
谷歌来的答案：
.球同，盒同，允许空箱
dp[n][m]=dp[n][m-1]+dp[n-m][m], n>=m
dp[n][m]=dp[n][m-1], n<m
边界dp[k][1]=1,dp[1][k]=1,dp[0][k]=1
现在有n个球，和m个箱子，我可以选择在所有箱子里面都放上1个球，也可以不选择这个操作。
如果选择了这个操作，那么就从dp[n-m][m]转移过来
如果没有选择这个操作，那么就从dp[n][m-1]转移过来