这是官方题解，写点感想。 1.这题妙不可言之处在将数据一般化，只提取出有用的期望步数 2.题解中关于如何从f[i]推出g[i]并没有证明，我给出的证明如下： 题解中说了当
i>=k
时，
f[i]=f[i−1]∗i+f[i+1]∗(n−i)n+1
那么，当
i>=k
时
g[i]=f[i]−f[i−1]
g[i]=f[i−1]∗i+f[i+1]∗(n−i)n+1−f[i−1]
g[i]=f[i−1]∗(i−n)+f[i+1]∗(n−i)n+1
g[i]=(n−i)∗(f[i+1]−f[i]+f[i]−f[i−1])n+1
g[i]=(n−i)∗(g[i+1]−g[i])n+1
g[i]=g[i+1]∗(n−i)i+n
,证毕 这是我滥用stl的代码
