题目：英雄升级，从0级升到1级，概率100%。
从1级升到2级，有1/3的可能成功；1/3的可能停留原级；1/3的可能下降到0级；
从2级升到3级，有1/9的可能成功；4/9的可能停留原级；4/9的可能下降到1级。
每次升级要花费一个宝石，不管成功还是停留还是降级。
求英雄从0级升到3级平均花费的宝石数目。
这个题目秒杀了一大片，一开始看到这个题目，立刻反应出来的是自动机DP，然后就朝着自动机DP去想，很快一个公式就可以搞出来。
dp[i][k]表示k步之后在i级的概率。
dp[0][k] = 1/3*dp[1][k-1];
dp[1][k] = dp[0][k-1]+1/3*dp[1][k-1] + 4/9*dp[2][k-1]
dp[2][k] = 1/3*dp[1][k-1] + 4/9* dp[2][k-1];
dp[3][k]= 1/9*dp[2][k-1];
然后此递推式可以写成矩阵乘法的形式，最后的结果就是求/Sigma (k+1)/9*dp[2][k]; 这个矩阵可以转换为对角阵，然后可以求出其通项公式等等。。。其实这个问题是线性差分方程组的解法。。。还要求特征值 + Jordan标准型bulalalalala。。。。我觉得要算出一个解析解的话果断是跪了。。。用Matlab跑了一下：
A =
0 1/3 0
1 1/3 4/9
0 1/3 4/9
>> ret =0;
>> for k=1:1000
ret = ret+ (k+1)/9*[0 0 1]*A^k*[1 0 0]';
end
>> ret
ret =
30
竟然是整数30.。。被赤果果得鄙视智商了。。。
蛋疼的用C++再跑一遍：
#include <stdio.h>
#include <iostream>
using namespace std;
double dp[4];
double nextdp[4];
int main()
{
for(int i=0; i<4; i++) dp[i]=0.0f;
dp[0]=1.0f;
double ret=0.0f;
for(int i=0; i<100000000; i++)
{
for(int j=0; j<4; j++) nextdp[j]=0.0f;
nextdp[0]= 1/3.0*dp[1];
nextdp[1]=1/3.0*dp[1]+dp[0]+4/9.0*dp[2];
nextdp[2]=4/9.0*dp[2]+1/3.0*dp[1];
nextdp[3]=1/9.0*dp[2];
ret+=i*dp[3];
for(int j=0; j<4; j++) dp[j]=nextdp[j];
if(i%1000000==0)
{
cout<<i<<" ";
printf("%d %.4f\n",i, ret);
}
}
return 0;
}
还是30.。。
于是想到有没有简单的方法。。。其实可以观察到当趋于无穷的时候，此系统的期望的概率转移是趋于稳定的！其实任何系统在无穷步之后，都是期望稳定的！！(废话,但很重要！)
所以，从0 到1 所需要的期望步数很简单就是1. 从1到2的期望步数假设是X ，则在走了一步之后，我们分情况讨论所处位置。可以列出 X = 1+ 1/3*X + 1/3*(1+X) 所以X=4 ,从1 都2 的期望步数是4. 同理，从2-3 X = 1+ 4/9*X + 4/9*(4+X) X =25. 从2到3的期望步数是25. 所以从0到3的期望步数是 30.。。。。。。。
坑爹啊！！！！！！！！！！！！
使用第一种思路可以求，问题是那个矩阵A太坑爹。。。看看他的特征值。。。。eig(A)
ans =
-1588/3201
1072/3461
457/474
还要带着n次方去求解dp[2][k]的通项。。。杀了我吧。。第二种方法是解决这类问题的万金油啊。反正系统达到稳态，那就直接上稳态公式吧。其实求解差分方程组的解法中，隐含使用的条件就是稳态方程。。。殊归同途啊。。。