本文主要是介绍邮票收集问题整理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
有n种类型的邮票，问将所有的类型的邮票全部收集起来所要的收集次数期望是多少。
分析
我们可以设dp[i]为已经收集了i种类型的票，还要收集n-i种的次数的期望。
那么显然dp[n]=0;
递推式子有:dp[i]=dp[i+1]∗(n−i)/n+dp[i]∗i/n+1dp[i]=dp[i+1]∗(n−i)/n+dp[i]∗i/n+1
化简可得
dp[i]=dp[i+1]+n/(n−i)dp[i]=dp[i+1]+n/(n−i)
再化简，公式就很显然了。
dp[0]=n(1/n+1/(n−1)+…+1/1)
这样我们就可以得到每张邮票所被拿的期望就是 (1/n+1/(n−1)+…+1/1) 。
这篇关于邮票收集问题整理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
