【ZOJ - 2949】Coins of Luck （概率dp，期望）

题干：

给你两种泡面 各N包，然后你扔硬币，正面朝上吃第一种，反面呢 吃第二种，有任意一种吃完时 就不需要抛硬币了，求停止抛硬币的期望。

Sample Input

2
1
2

Sample Output

1.00
2.50

解题报告：

   dp[i][j]代表i包第一种和j包第二种，抛硬币的期望，考虑最后吃的最后一包，于是分别由dp[i-1][j]和dp[i][j-1]等可能性转移而来。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

int n;
double dp[1010][1010];
int main()
{
	int t,q,i,j,k,cnt,t1,t2;
	char op[20];
	for(j=1;j<=1000;j++){
		for(k=1;k<=1000;k++){
			dp[j][k]=0.5*(dp[j-1][k]+dp[j][k-1])+1.0;
		}
	}
	cin>>t;
	for(i=1;i<=t;i++){
		scanf("%d",&n);
		printf("%.2f\n",dp[n][n]);
	}

	return 0;
}