題目：英雄升級(jí)，從0級(jí)升到1級(jí)，概率100%。
從1級(jí)升到2級(jí)，有1/3的可能成功；1/3的可能停留原級(jí)；1/3的可能下降到0級(jí)；
從2級(jí)升到3級(jí)，有1/9的可能成功；4/9的可能停留原級(jí)；4/9的可能下降到1級(jí)。
每次升級(jí)要花費(fèi)一個(gè)寶石，不管成功還是停留還是降級(jí)。
求英雄從0級(jí)升到3級(jí)平均花費(fèi)的寶石數(shù)目。
這個(gè)題目秒殺了一大片，一開(kāi)始看到這個(gè)題目，立刻反應(yīng)出來(lái)的是自動(dòng)機(jī)DP，然后就朝著自動(dòng)機(jī)DP去想，很快一個(gè)公式就可以搞出來(lái)。
dp[i][k]表示k步之后在i級(jí)的概率。
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];
然后此遞推式可以寫(xiě)成矩陣乘法的形式，最后的結(jié)果就是求/Sigma (k+1)/9*dp[2][k]; 這個(gè)矩陣可以轉(zhuǎn)換為對(duì)角陣，然后可以求出其通項(xiàng)公式等等。。。其實(shí)這個(gè)問(wèn)題是線性差分方程組的解法。。。還要求特征值 + Jordan標(biāo)準(zhǔn)型bulalalalala。。。。我覺(jué)得要算出一個(gè)解析解的話果斷是跪了。。。用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
竟然是整數(shù)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.。。
于是想到有沒(méi)有簡(jiǎn)單的方法。。。其實(shí)可以觀察到當(dāng)趨于無(wú)窮的時(shí)候，此系統(tǒng)的期望的概率轉(zhuǎn)移是趨于穩(wěn)定的！其實(shí)任何系統(tǒng)在無(wú)窮步之后，都是期望穩(wěn)定的??！(廢話,但很重要！)
所以，從0 到1 所需要的期望步數(shù)很簡(jiǎn)單就是1. 從1到2的期望步數(shù)假設(shè)是X ，則在走了一步之后，我們分情況討論所處位置?？梢粤谐?#160; X = 1+ 1/3*X + 1/3*(1+X) 所以X=4 ,從1 都2 的期望步數(shù)是4. 同理，從2-3 X = 1+ 4/9*X + 4/9*(4+X) X =25. 從2到3的期望步數(shù)是25. 所以從0到3的期望步數(shù)是 30.。。。。。。。
坑爹?。。。。。。。。。。。?！
使用第一種思路可以求，問(wèn)題是那個(gè)矩陣A太坑爹。。。看看他的特征值。。。。eig(A)
ans =
-1588/3201
1072/3461
457/474
還要帶著n次方去求解dp[2][k]的通項(xiàng)。。。殺了我吧。。第二種方法是解決這類(lèi)問(wèn)題的萬(wàn)金油啊。反正系統(tǒng)達(dá)到穩(wěn)態(tài)，那就直接上穩(wěn)態(tài)公式吧。其實(shí)求解差分方程組的解法中，隱含使用的條件就是穩(wěn)態(tài)方程。。。殊歸同途啊。。。