算法----bonus dumplings - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
Read full article from 算法----bonus dumplings - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
过年了，妈妈做了100只饺子，其中有10只饺子里面有1块的硬币。
小明依次吃这100只饺子，如果小明连续吃到k个硬币，那么小明得到k-1个硬币。
小明依次吃这100只饺子，如果小明连续吃到k个硬币，那么小明得到k-1个硬币。
e.g. 110111表示6只饺子，1表示有硬币，0表示没有。11表示连续吃到2个饺子，那么小明得1个硬币；111连续迟到3个，小明得2个硬币；故，小明共得到3个硬币。
问小明得到的硬币的期望值是多少？
分析
期望定义： E(X)=∑iXiP(Xi)
在本题中，随机事件X即为小明最终得到的硬币数目，x∈[0,9]
- 计算
P(Xi)=cases(x=i)allcases - 计算期望
那么原问题就简化为小明得到硬币k,所有可能的cases的数目。
采用动态规划，子问题定义如下
- f[i][j][k]――前i个饺子，含j个有硬币的饺子，得分是k，且第i个饺子不含硬币，所有可能的情况的总数。
- g[i][j][k]――前i个饺子，含j个有硬币的饺子，得分是k，且第i个饺子含硬币，所有可能的情况的总数。
那么递推公式如下,
- f[i][j][k]―-第i个饺子不包含硬币，所以不用第i个饺子
- f[i][j][k] = f[i-1][j][k] + g[i-1][j][k]
- g[i][j][k]―-第i个饺子包含硬币，那么这个硬币能够得到，取决于第i-1个饺子是否包含硬币
- g[i][j][k] = f[i-1][j-1][k] + g[i-1][j-1][k-1]
Read full article from 算法----bonus dumplings - L.J.SHOU的专栏 - 博客频道 - CSDN.NET
