简单题[期望DP]

也许更好的阅读体验
$Description$Description
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
$Solution$Solution

设 $f\left[i\right]\left[j\right]$f[i][j]表示有 $i$i张红牌， $j$j张黑牌的期望收益
考虑翻一张牌，有两种情况

1. 有 $\frac{i}{i+j}$i+ji​的概率翻到红牌，此后就只有 $i-1$i−1张红牌， $j$j张黑牌
2. 有 $\frac{j}{i+j}$i+jj​的概率翻到黑牌，此后就只有 $i$i张红牌， $j-1$j−1张黑牌

需要注意的是，不要忘了翻开的牌的贡献
翻开一张牌后，该颜色牌数目就少了一张

所以有
$f\left[i\right]\left[j\right]=\frac{i}{i+j}\left(f\right[i-1\left]\right[j]+1)+\frac{j}{i+j}\left(f\right[i\left]\right[j-1]-1)$f[i][j]=i+ji​(f[i−1][j]+1)+i+jj​(f[i][j−1]−1)
由于是最优策略，所以咱是不可能赔钱的
$f\left[i\right]\left[j\right]=max(0,\frac{i}{i+j}(f[i-1]\left[j\right]+1)+\frac{j}{i+j}(f\left[i\right][j-1]-1\left)\right)$f[i][j]=max(0,i+ji​(f[i−1][j]+1)+i+jj​(f[i][j−1]−1))

初值 $f\left[0\right]\left[1\right]=0,f\left[1\right]\left[0\right]=1$f[0][1]=0,f[1][0]=1，答案为 $f\left[R\right]\left[B\right]$f[R][B]
应正向循环

本篇博客亦被收进期望总结

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧