# [TopCoder9915]RedIsGood（动态规划，期望概率）

### Description

You have a deck that contains R red and B black cards.
You are playing the following game: You shuffle the deck, and then begin dealing the cards one by one. For each red card you flip you get a dollar, and for each black card you flip you have to pay a dollar. At any moment (including the beginning of the game) you are allowed to stop and keep the money you have.
Write a method that will take the ints R and B, and return the expected amount you will gain if you play this game optimally.

## 解决思路

$F[i][j]=max(0,\frac{i}{i+j}*(F[i-1][j]+1)+\frac{j}{i+j}*(F[i][j-1]-1)$

## 代码

class RedIsGood
{
public:
double F[maxN][maxN];
double getProfit(int R, int B){
F[0][0]=0;
for (int i=0;i<=R;i++)
for (int j=0;j<=B;j++)
{
if ((i==0)&&(j==0)) continue;
if (i==0) F[i][j]=0;
else if (j==0) F[i][j]=F[i-1][j]+1;
else F[i][j]=max(0.0,(1.0*i/(i+j)*(F[i-1][j]+1)+1.0*j/(i+j)*(F[i][j-1]-1)));
}
return F[R][B];
}
};


class RedIsGood
{
public:
double F[maxN];
double getProfit(int R, int B){
for (int i=0;i<=R;i++) F[i]=i;
for (int j=1;j<=B;j++)
for (int i=0;i<=R;i++)
F[i]=max(0.0,(1.0*i/(i+j)*(F[i-1]+1)+1.0*j/(i+j)*(F[i]-1)));
return F[R];
}
};


HNCJ OIer