#24582: 簡單的規律


d10932027@gapps.fg.tp.edu.tw (雯貓)

School : 臺北市立第一女子高級中學
ID : 132566
IP address : [111.241.103.188]
Last Login :
2021-08-06 13:53:41
b229. TOI2009 第一題:路徑問題 -- 2009TOI研習營初選 | From: [122.116.35.159] | Post Date : 2021-03-06 22:02

f(1) = 3;

f(2) = 7;

f(n) = f(n-1)*2+f(n-2);

用遞迴方式會TLE,所以要用陣列寫

 

原因:

n-1的時候有f(n-1)條路徑

其中如果某條路徑最後一步是向上的話,第n步就會衍生出3種可能。如果某條路徑最後一步是向左或向右,則第n步就會衍生出2種可能

那f(n-1)條路徑中,有幾條路徑最後一步是向上呢?

往回追溯,第n-2步時,會有f(n-2)條路徑。而在n-1步時,f(n-2)條路徑都能繼續向上。

也就是說,f(n-1)條路徑中,有f(n-2)條路徑最後一步是向上的

所以f(n) = f(n-2)*3+(f(n-1)-f(n-2))*2 = f(n-1)*2+f(n-2)

 
ZeroJudge Forum