題目：英雄升級，從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]的通項。。。殺了我吧。。第二種方法是解決這類問題的萬金油啊。反正系統達到穩態，那就直接上穩態公式吧。其實求解差分方程組的解法中，隱含使用的條件就是穩態方程。。。殊歸同途啊。。。