期望DP（2013山东省赛）

题意：有N行房间，整个排列呈三角形。

如图：      1

           2    3

         4   5   6

     7    8    9   10

 11  …………………   15  

第一行一个，第二行两个，第三行……第N行N个，起点是第一行第一个，终点是第N行第一个。每次只能进入同一行左边那个房间，或者下一行左侧，或者下一行右侧的房间。显然有些位置只有进入左下，或右下的可能，给出概率分别为a,b(a+b=1)，有些位置可以有左侧，左下，右下3种可能，给出概率分别为c,d,e(c+d+e=1)，求从起点出发到终点的期望。

简单的求期望。求期望从终点先考虑，设dp[i][j]表示处在第i行第j个位置的房间时，走到终点还需要的步数期望。显然dp[n][0]=0，因为已经在终点了显然不需要再走了，我们要求的显然是dp[1][0]。首先转移的第一步初始化是最后一行，因为最后一行只能往左走了，所以dp[n][i]=dp[n][i-1]+1，对于每行最左边那个数，只有两种可能的走法，所以dp[i][0]=a*dp[i+1][0]+b*dp[i+1][1]+1，其他位置则有三种可能的走法，所以dp[i][j]=c*dp[i+1][j]+d*dp[i+1][j+1]+e*dp[i][j-1]+1（记住这里每次求期望最后都要+1）具体代码如下:

#include <stdio.h>
#include <string.h>
#include <algorithm>
double dp[50][50];
int main()
{
    int n;
    while(scanf("%d",&n))
    {
        if(n==0)break;
        double a,b,c,d,e;
        scanf("%lf %lf %lf %lf %lf",&a,&b,&c,&d,&e);
        dp[n][0]=0;
        for(int i=1; i<n; i++)dp[n][i]=dp[n][i-1]+1;
        for(int i=n-1; i>=1; i--)
        {
            dp[i][0]=dp[i+1][0]*a+dp[i+1][1]*b+1;
            for(int j=1; j<n; j++)
            {
                dp[i][j]=dp[i+1][j]*c+dp[i+1][j+1]*d+dp[i][j-1]*e+1;
            }
        }
        printf("%.2lf
",dp[1][0]);
    };
    return 0;
}