定义f[i]f[i]f[i]表示还剩iii个关键键没按,按完的期望
原式f[i]=inf[i−1]+n−in∗f[i+1]+1f[i]=\frac{i}{n}f[i-1]+\frac{n-i}{n}*f[i+1]+1f[i]=nif[i−1]+nn−i∗f[i+1]+1
移项f[i+1]=nn−if[i]−in−if[i−1]−nn−if[i+1]=\frac{n}{n-i}f[i]-\frac{i}{n-i}f[i-1]-\frac{n}{n-i}f[i+1]=n−inf[i]−n−iif[i−1]−n−in
用iii替换i+1i+1i+1得f[i]=nn−i+1f[i−1]−i−1n−i+1f[i−2]−nn−i+1f[i]=\frac{n}{n-i+1}f[i-1]-\frac{i-1}{n-i+1}f[i-2]-\frac{n}{n-i+1}f[i]=n−i+1nf[i−1]−n−i+1i−1f[i−2]−n−i+1n
得到递推式f[i]=1n−i+1∗(nf[i−1]−(i−1)f[i−2]−n)f[i]=\frac{1}{n-i+1}*(nf[i-1]-(i-1)f[i-2]-n)f[i]=n−i+11∗(nf[i−1]−(i−1)f[i−2]−n)
这个式子有问题吗
我和题解算出来结果好像不一样...