题目链接：https://codeforces.com/contest/1245/problem/E
题意：有一个10x10的网格，左下角是起点，左上角是终点，从起点开始，如图所示蛇形走到终点，每一步走的时候要摇骰子，骰子是几就走几步，但是到终点前的那6步，骰子必须是直接到终点的步数才能走过去，否则原地停留，题中还有一个条件，可能有一些网格上存在梯子，你可以直接沿着梯子到更高的一行，求从起点到终点的最小平均摇骰子的次数。
题解：这是一道明显的概率dp题，dp[i]表示到第i格子终点所需的期望,从后往前枚举。
考虑终点前的六个方格，每次只能是骰子 = 到终点的步数才能移动，所以前六格的dp[i] = 6。
剩余的方格就是用期望dp的套路解决，因为骰子有六种可能，枚举每次可以达到的这六种状态就行，每个状态都乘一个1/6，因为每次到达的方格可能直接沿梯子走到更靠上的方格x，所以这直接等价于梯子可以上去的方格dp[x] , 假设我要走step步，每次两者 dp[i-step]和dp[x] 相比要取一个min去更新dp[i]。
最终转移方程为 dp[i] = min(dp [ i-step ]，dp[index[i-step] ] )
AC代码：
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e2+5;
int index[15][15],grid[maxn];
double dp[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int i = 0;i<10;i++){
for(int j = 0;j<10;j++){
if(i%2 == 0) index[i][j] = i*10 + j;
else index[i][j] = i*10+(9 - j); //给方格构造一个index值，从0-99
}
}
for(int i = 0;i<10;i++){
for(int j = 0;j<10;j++){
int t;
cin>>t;
if(t == 0) grid[index[i][j]] = index[i][j];
else grid[index[i][j]] = index[i-t][j];//记录每个方格的index值，梯子能上去的方格
//两者index相等
}
}
dp[0] = 0;
for(int i = 1;i<=6;i++) dp[i] = 6;
for(int i = 7;i<100;i++){
double sum = 0;
for(int j = 1;j<=6;j++){
sum = sum + min(dp[i-j],dp[grid[i-j]]);//状态转移方程
}
dp[i] = (sum/6)+1;
}
printf("%.10lf",dp[99]);
return 0;
}