SGU495KidsandPrizes概率DP，期望公式

题目

这题目首先进去以后，没地方提交，第一次做SGU的题目，只能在HUSTOJ上提交了

有n个盒子，里面有&＃31036;物的，m个人，每个人拿，拿过以后 把&＃31036;物取出来 把盒子放回去，求选中&＃31036;物数的期望

其实一开始就假设方程 dp[i]为 第i个人获得&＃31036;物的概率，但是状态转移方程不知道该怎么办，想了很久都没有办法，

其实首先边界为dp[1] = 1 第一个上来选的人肯定必中

接下来一个人的 则由两部分组成，dp[i] = (1 - dp[i - 1]) * dp[i - 1] &＃43; .........，因为上一个人若没有选中，那么这一次选中的概率跟是上一个一样的，那么如果上一个人选中了呢，真的是想了好久好久啊，可是没有思路，，最后没办法，看了别的博客，那个人用了一个公式的方法做的，但是我觉得概率DP可以推的，看他介绍，一开始就强调了m个人选&＃31036;物是相互独立的事件，呃，这时候我有点开窍了，概率论学了很久了，有点忘了，每一次当一个&＃31036;物被选走的时候，人们选中&＃31036;物的概率都会减少1/n，这么说吧，我的理解是一开始选就是n个里面选一个，再后来少了一个&＃31036;物，那选中的概率就少了1/n，比如一开始有五个&＃31036;物，那么一开始选中的的概率为1，第二次按照我所想就是4/5，实际上确实 是只剩下四个&＃31036;物了，但是空盒子还是有一个的，所以一个人选中的概率为4/5，前面做多了，后来我一直以为是1/4，忘了总体，前面人选走&＃31036;物 对于这次 你的选择没有影响，因为你还是在那么多盒子里选，总得选得范围并没有发生变化，那么这样方程另一部分就出来了

dp[i] = (1 - dp[i - 1]) * dp[i - 1] &＃43; dp[i - 1] * (dp[i - 1] - 1/n)//对这个有点疑问的，题目没说n比m大，万一n比m小，一直减，会不会为负？

应该是我想多了，后面被拿完了&＃31036;物，那么一直都是0了，就算是负的乘以0也是一样的

那么这样m个人每个人 获得&＃31036;物的概率都求出来了，如何求期望呢？哈哈真的不会唉，概率忘光了...我当时的想法就是 每个人的概率乘以1然后累加，尝试了案例是对了，交了以后就过了。。。到底是为什么捏，看了别人博客都没有给出解释。。。百度了一会独立事件的期望，有个n * p的我都知道的方法，还发现了一个二项分布的计算方法，这个我是忘了，但是稍微画了一会，发现 跟这道题还是没有联系上，路过的巨巨 请给个解释，太晚了，明天自己再研究研究

int n,m;

double dp[100000 + 55];

void init() {

}

bool input() {
	while(cin>>n>>m) {

		return false;
	}
	return true;
}

void cal() {
	dp[1] = 1.00;
	for(int i=2;i<=m;i++)
		dp[i] = dp[i - 1] * (dp[i - 1] - 1.00/n*1.0) + dp[i - 1] * (1 - dp[i - 1]);
	double ans = 0.00;
	for(int i=1;i<=m;i++)
		ans += dp[i] * 1.00;
	printf("%.10lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

哎呀，写完题解以后，走之前又手贱的试了一把，嗯发现这样也是可以的，就是每一步都加一个步数1，跟以前图里走步数其实是一样的，因为dp[i]代表的是选中的概率，那么肯定是选中的，所以加1就没问题了，那么加1状态方程就变成了，dp[i]代表的是前i个人选&＃31036;物数目的期望，直到dp[m]就是答案，但是这样其它方向一想有点问题了，这样不是m步了吗？跟&＃31036;物数什么联系呢？其实没事，如果n大于m，那么其实你最多选m个&＃31036;物，如果n小于m，那么后来的概率是有为0的，所以你这样加上去，在下一步的乘法又变成了0，乱七八糟，否定自己以后又肯定自己，呵呵，好烦啊，睡觉去了。。。

int n,m;

double dp[100000 + 55];

void init() {

}

bool input() {
	while(cin>>n>>m) {

		return false;
	}
	return true;
}

void cal() {
	dp[1] = 1.00;
	for(int i=2;i<=m;i++)
		dp[i] = dp[i - 1] * (dp[i - 1] - 1.00/n*1.0) + dp[i - 1] * (1 - dp[i - 1]) + 1;
	//double ans = 0.00;
	//for(int i=1;i<=m;i++)
	//	ans += dp[i] * 1.00;
	printf("%.10lf\n",dp[m]);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

最后n个&＃31036;物都不被选中的期望为 n *( (n - 1)/n)^m,

那么选中&＃31036;物 的 期望为n -  n *( (n - 1)/n)^m,哈哈,跪了，啥好都不如数学好啊，想了那么久，人家一句话 简单概率期望公式 就解决了，呵呵

int n,m;

double dp[100000 + 55];

void init() {

}

bool input() {
	while(cin>>n>>m) {

		return false;
	}
	return true;
}

void cal() {
	double ans = n * 1.00;
	double tmp = 1.00;
	for(int i=1;i<=m;i++) {
		tmp *= (n - 1)*1.0/n*1.0;
	}
	ans = ans - n * tmp;
	printf("%.10lf\n",ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}