一直不明白为什么概率是正推，期望是逆推。 现在题目做多了，慢慢好像有点明白了
poj2096
收集bug， 有n个种类的bug，和s个子系统。 每找到一个bug需要一天。
要我我们求找到n个种类的bug，且在每个系统中都找到一个bug的期望天数
设dp[i][j] 为找到i个种类的bug和在j个系统中找到bug后，还需要的期望天数
那么dp[n][s] 肯定是0，而dp[0][0]是我们要求的。 这也就是为什么期望是要逆推。
还有一点就是这一状态的期望会等于 所有（下一状态的的期望*这一状态走向下一状态的概率）的和+1
所有可能的情况如下
找到了一个新种类的bug (n-i)/n 第一维度增加1,在一个已经找到bug的系统里面j/s， 第二维度不增加
找到了一个旧种类的bug i/n 第一维度不增加，在一个没有找到bug的系统里面 (s-j)/s 第二维度增加，
找到了一个新种类的bug (n-i)/n 第一维度增加，在一个没有找到bug的系统里面 (s-j)/s 第二维度增加，
找到了一个旧种类的bug i/n 第一维度不增加 ， 在一个已经找到bug的系统里面 j/s 第二维度不增加
所有状态转移方程是
dp[i][j] = (1-i/n)*j/s*dp[i+1][j] + i/n*(1-j/s)*dp[i][j+1] + (1-i/n)*（1-j/s) * dp[i+1][j+1] + i/n*j/s*dp[i][j] + 1
将红色的部分移到左边化简后得到
dp[i][j] = （(1-i/n)*j/s*dp[i+1][j] + i/n*(1-j/s)*dp[i][j+1] + (1-i/n)*（1-j/s) * dp[i+1][j+1] +1）/(1-i/n*j/s)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = << ;
/*
double dp[n][s] 表示已经找到n个种类的bug，在s个子系统中都找到了bug的期望天数 找到了一个新种类的bug (n-i)/n 第一维度增加1,在一个已经找到bug的系统里面j/s， 第二维度不增加
找到了一个旧种类的bug i/n 第一维度不增加，在一个没有找到bug的系统里面 (s-j)/s 第二维度增加，
找到了一个新种类的bug (n-i)/n 第一维度增加，在一个没有找到bug的系统里面 (s-j)/s 第二维度增加，
找到了一个旧种类的bug i/n 第一维度不增加 ， 在一个已经找到bug的系统里面 j/s 第二维度不增加 dp[i][j] = (1-i/n)*j/s*dp[i+1][j] + i/n*(1-j/s)*dp[i][j+1] + (1-i/n)*（1-j/s) * dp[i+1][j+1] + i/n*j/s*dp[i][j] dp[i][j] = （(1-i/n)*j/s*dp[i+1][j] + i/n*(1-j/s)*dp[i][j+1] + (1-i/n)*（1-j/s) * dp[i+1][j+1] +1）/(1-i/n*j/s) */
double dp[ + ][ + ];
int main()
{ int n, s;
while (scanf("%d%d", &n, &s) != EOF)
{
memset(dp, , sizeof(dp));
dp[n][s] = ;
for (int i = n; i >= ; --i)
{
for (int j = s; j >= ; --j)
{
if (i == n &&j == s)continue;
dp[i][j] += ( - (double)i / n)*j / s*dp[i + ][j] + (double)i / n*( - (double)j / s)*dp[i][j + ] + ( - (double)i / n)*( - (double)j / s)*dp[i + ][j + ] + ;
dp[i][j] /= ( - (double)i / n*j / s);
}
}
printf("%.4lf\n", dp[][]);
}
return ;
}
hdu4405
给我们n+1个格子， 标号0到n，一个人初始在位置0，然后丢骰子向前走，
然后又给定m个 a b ， 表示到了位置a，能够到飞到位置b而不需要丢骰子
问走到>=n的位置 需要丢骰子的期望次数
设dp[i] 为从位置i到>=n的位置需要丢骰子的期望次数
dp[i>=n] = 0
dp[i] = 1/6 * dp[i+1] + 1/6*dp[i+2] + ... + 1/6 * dp[i+6]
如果位置i+k 能够飞行， 那么应该用飞行过后的位置的期望带入去算
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
dp[i>=n] = 0;
dp[i] = dp[i+k] * 1/6
*/
double dp[ + ];
int hs[ + ];
int main()
{
int n, m;
int x, y;
while (scanf("%d%d", &n, &m), n)
{
memset(dp, , sizeof(dp));
memset(hs, , sizeof(hs));
for (int i = ; i < m; ++i)
{
scanf("%d%d", &x, &y);
hs[x] = y;
}
for (int i = n-; i >= ; --i)
{
dp[i] = ;
for (int k = ; k <= ; ++k)
{
if (hs[i + k] != )
{
int t = i + k;
while (hs[t] != )//找到飞行的最终位置， 因为能够多次飞行
{
t = hs[t];
}
dp[i] += dp[t] / ;
}
else
dp[i] += dp[i + k] / ;
}
}
printf("%.4lf\n", dp[]);
}
return ;
}
hdu3853
一个人在迷宫的位置（1,1） 要逃到 迷宫的位置（n,m）
在位置（i,j） 需要2魔力去开启传送阵， 有p1的概率是留在原地， p2的概率往右走,p3的概率往下走
问我们逃到迷宫的位置(n,m)需要的魔力的期望
dp[i][j] = p1 * dp[i][j] + p2*dp[i][j+1] + p3*dp[i+1][j] + 2
dp[i][j] = ( p2*dp[i][j+1] + p3*dp[i+1][j] + 2 ) / (1-p1)
还有一个坑是如果某点停留在原地的概率为1， 这是允许的， 那么肯定所有的点都不会到达这一点，否则答案就会很大，不符合题目所说的
所以应该讲该点的dp[i][j]置为0， 而不应该去计算（万一计算出来很大呢）不然会影响之后的值， 因为虽然走到该点的概率是0， 但是浮点数毕竟有误差。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
dp[i][j] = 2 + dp[i][j+1] * p[i][j][1] + dp[i+1][j] * p[i][j][2] + dp[i][j] * p[i][j][0]
dp[i][j] = (2 + dp[i][j+1]*p[i][j][1] + dp[i+1][j] * p[i][j][2])/(1-P[i][j][0]);
*/
const int N = + ;
double p[N][N][];
double dp[N][N];
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j)
for (int k = ; k < ; ++k)
scanf("%lf", &p[i][j][k]);
dp[n][m] = ;
for (int i = n; i >= ; --i)
{
for (int j = m; j >= ; --j)
{
if (i == n &&j == m)
continue;
if (fabs( - p[i][j][]) <= 1e-)//如果该点停留在原地的概率为1， 这是允许的， 那么肯定所有的点都不会到达这一点，否则答案就会很大，不符合题目所说的
{
dp[i][j] = ;
continue;
}
dp[i][j] = (p[i][j][] * dp[i][j + ] + p[i][j][] * dp[i + ][j]) / ( - p[i][j][]) + /(-p[i][j][]);
}
}
printf("%.3lf\n", dp[][]);
}
return ;
}