题目链接：http://codeforces.com/problemset/problem/148/D
题意：
一个袋子中有w只白老鼠，b只黑老鼠。
公主和龙轮流从袋子里随机抓一只老鼠出来，不放回，公主先拿。
公主每次抓一只出来。龙每次在抓一只出来之后，会随机有一只老鼠跳出来（被龙吓的了。。。）。
先抓到白老鼠的人赢。若两人最后都没有抓到白老鼠，则龙赢。
问你公主赢的概率。
题解：
表示状态：
dp[i][j] = probability to win（当前公主先手，公主赢的概率）
i：剩i只白老鼠
j：剩j只黑老鼠
找出答案：
ans = dp[w][b]
边界条件：
if i==0 dp[i][j] = 0 （没有白老鼠了，不可能赢）
else if j==0 dp[i][j] = 1 （有且只有白老鼠，一定赢）
else if j==1 dp[i][j] = i/(i+1) （如果公主拿了黑老鼠，那么龙一定会拿到白老鼠，公主输。所以公主一下就要拿到白老鼠）
如何转移：
对于dp[i][j]，有两种赢的方法：
（1）公主在这个回合一次就抓到了白老鼠。
（2）公主和龙都各抓了一只黑老鼠，然后公主在下一个回合赢了。
P（一次就抓到了白老鼠） = i/(i+j)
P（进入下个回合，即两人都抓到黑老鼠） = P（公主抓到黑老鼠） * P（龙抓到黑老鼠） = j/(i+j) * (j-1)/(i+j-1)
所以dp[i][j] = P（一次就抓到了白老鼠） + P（进入下个回合） * P（在下个回合赢）
那么考虑下个回合可能的状态。
因为公主和龙都已经抓走了两只黑老鼠，那么下个回合取决于跳出来的老鼠，有三种可能：
（1）跳出来白老鼠
（2）跳出来黑老鼠
（3）老鼠已经抓完了，没有老鼠跳出来
对于情况（3），原状态(i,j)只可能为：(1,1) , (0,2) , (2,0)，均包含在边界条件中，所以不作考虑。
剩下两种情况的可能性：
（1）P（跳出来白老鼠） = i/(i+j-2) (i>=1 and j>=2)
（2）P（跳出来黑老鼠） = (j-2)/(i+j-2) (j>=3)
所以P（在下个回合赢） = P（跳出来白老鼠） * dp[i-1][j-2] + P（跳出来黑老鼠） * dp[i][j-3]
总方程：
nex = 0
if i>=1 and j>=2 nex += i/(i+j-2)*dp[i-1][j-2]
if j>=3 nex += (j-2)/(i+j-2)*dp[i][j-3]
dp[i][j] = i/(i+j) + j/(i+j) * (j-1)/(i+j-1) * nex
另外，这道题的题解有两个版本，一种记忆化搜索，一种for循环版，都差不多。
AC Code（记忆化搜索）:
// state expression:
// dp[i][j] = probability to win
// i: i white mice
// j: j black mice
//
// find the answer:
// ans = dp[w][b]
//
// transferring:
// if i>=1 and j>=2 nex += i/(i+j-2)*dp[i-1][j-2]
// if j>=3 nex += (j-2)/(i+j-2)*dp[i][j-3]
// dp[i][j] = i/(i+j) + j/(i+j) * (j-1)/(i+j-1) * nex
//
// boundary:
// if i==0 dp[i][j] = 0
// if j==0 dp[i][j] = 1
// if j==1 dp[i][j] = i/(i+1)
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005 using namespace std; int w,b;
bool vis[MAX_N][MAX_N];
double ans;
double dp[MAX_N][MAX_N]; double dfs(int i,int j)
{
if(vis[i][j]) return dp[i][j];
vis[i][j]=true;
if(i==) return dp[i][j]=;
if(j==) return dp[i][j]=;
if(j==) return dp[i][j]=(double)i/(i+);
double nex=;
nex+=(double)i/(i+j-)*dfs(i-,j-);
if(j>=) nex+=(double)(j-)/(i+j-)*dfs(i,j-);
return dp[i][j]=(double)i/(i+j)+(double)j/(i+j)*(j-)/(i+j-)*nex;
} void read()
{
cin>>w>>b;
} void solve()
{
memset(vis,false,sizeof(vis));
ans=dfs(w,b);
} void print()
{
printf("%.9f\n",ans);
} int main()
{
read();
solve();
print();
}
AC Code（for循环）:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005 using namespace std; int w,b;
double ans;
double dp[MAX_N][MAX_N]; void read()
{
cin>>w>>b;
} void solve()
{
memset(dp,,sizeof(dp));
for(int i=;i<=w;i++)
{
for(int j=;j<=b;j++)
{
if(i==)
{
dp[i][j]=;
continue;
}
if(j==)
{
dp[i][j]=;
continue;
}
if(j==)
{
dp[i][j]=(double)i/(i+);
continue;
}
double nex=(double)i/(i+j-)*dp[i-][j-];
if(j>=) nex+=(double)(j-)/(i+j-)*dp[i][j-];
dp[i][j]=(double)i/(i+j)+(double)j/(i+j)*(j-)/(i+j-)*nex;
}
}
} void print()
{
printf("%.9f\n",dp[w][b]);
} int main()
{
read();
solve();
print();
}