Red is good 题解

题目

这是一道典型概率dp..

设给了 n 张红牌和 m 张黑牌..

最初看到这道题的我——最优策略..??? 随便停下..???

对于这道题的认识一开始有一些误区..发现网上的一些题解写的也很模糊..

1. 首先,我一开始为了读懂样例，自己在纸上枚举，把翻牌的个数啊..黑牌出现的位置啊..都手模了一遍..最后欣喜地发现  --  完全不对..

2. 其次，我们会发现：诶？为什么红牌个数比黑牌少还要翻牌..?而且最优策略有的还是个正值..???

最后..我们可以对样例分析到：

当我们在前五张翻到的牌全部为红牌时 --- 不再翻牌！到此为止 。发现钱数为5，并且概率为 1/6  ;

若是我们在前五张就翻到了黑牌，发现后面全都是红牌，稳赚不亏！！！

相信大家的理解更加通透了一些..

接下来我们来想状态转移方程..

要求期望，所以选择逆推..

我们可以设 f[i][j] 为翻了 i 张红牌和 j 张黑牌之后，所得到的最佳期望值..(可理解为还剩下 i 张红牌和 j 张黑牌没有翻)

注意！！是在翻了之后才得到的值！！

我们是在根据已经翻的数据计算即将翻并且现在还没有翻的 f[i][j]！

最后我们得到了 f[n][m] ..

接下来是方程..

希望大家可以在这里明确一下：我们 f[i][j] 所计算出来的期望值，是由于红牌黑牌不同顺序而导致的各个值

我们没有翻这 i 张红牌和 j 张黑牌..

所以红牌的概率即为 i/(i+j)..

结束.

Red is good 题解

原文：https://www.cnblogs.com/woxiang/p/14799718.html