Java教程

磕瓜子 题解

本文主要是介绍磕瓜子 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

小L每次都会从这堆瓜子中挑出一粒,他每次吃完一粒瓜子后,就会得到两瓣瓜子壳,他会把瓜子壳也丢进瓜子堆里面去。

如果他拿到了自己之前吃瓜子留下的瓜子壳,他就会把拿到的瓜子壳丢掉,否则就吃掉拿到的瓜子并且把瓜子壳丢进去。

现在设每次小L拿到每一粒瓜子或者是瓜子壳的概率是均等的,问小L期望多少次能够把瓜子拿完。

思路简述

很简单的期望dp。

令 \(dp_{i,j}\) 表示还剩 \(i\) 个瓜子和 \(j\) 个瓜子壳的吃完所有瓜子的期望步数。

转移方程:\(dp_{i,j}=dp_{i-1,j+2}\times \frac{i}{i+j} + dp_{i,j-1}\times \frac{j}{i+j} +1\)

The End.

这篇关于磕瓜子 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!