题目：给出1-n连续的方格，从0开始，每一个格子有4个状态，左右脚交替，向右跳，而且每一步的步长必须在给定的区间之内。当跳出n个格子或者没有格子可以跳的时候就结束了，求出游戏的期望步数
0：表示不能到达这个格子
1：表示左脚跳进这个格子
2：表示右脚跳进这个格子
3：随意哪个脚跳进这个格子，而且下一步随意用哪个脚
dp[i][j] ：表示走到第 i 个格子在 j 状态的期望。
当j=1时，你可以走到dp[i+k][2],dp[i+k][3]，
当j=2时，你可以走到dp[i+k][1],dp[i+k][3]，
当j=3时，你可以走到dp[i+k][2],dp[i+k][3],dp[i+k][1]，
概率dp专题一波走起
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
double dp[][];
double p[][];
int main(){
int t,a,b,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&a,&b);
for(int i=;i<=n;i++)
for(int j=;j<;j++)
scanf("%lf",&p[i][j]);
for(int i=n+;i<=n+a;i++)
for(int j=;j<;j++)
p[i][j]=(j==);
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++){
double p1=,p2=,p3=;
for(int j=a;j<=b;j++){
dp[i+j][]+=dp[i][]*p1*p[i+j][];
dp[i+j][]+=dp[i][]*p1*p[i+j][];
p1*=(p[i+j][]+p[i+j][]);
dp[i+j][]+=dp[i][]*p2*p[i+j][];
dp[i+j][]+=dp[i][]*p2*p[i+j][];
p2*=(p[i+j][]+p[i+j][]);
dp[i+j][]+=dp[i][]*p3*p[i+j][];
dp[i+j][]+=dp[i][]*p3*p[i+j][];
dp[i+j][]+=dp[i][]*p3*p[i+j][];
p3*=p[i+j][];
// cout<<dp[i+j][1]<<" "<<dp[i+j][2]<<" "<<dp[i+j][3]<<endl;
}
}
double ans=;
for(int i=;i<=n+a;i++)
for(int j=;j<;j++)
ans+=dp[i][j];
printf("%.8f\n",ans);
}
return ;
}