#55612: 狀態轉移


Ixcy (Ixcy)


現在我們想要長度為n

若長度為n-3,可以用2個L補足,有2種補法

若長度為n-2,可以用1個L與1個單位補足,有4種補法

若長度為n-1,可以用2個單位補足,有1種補法

可以證明他們所構建的圖形並不重複且覆蓋所有情形(當然我也不會證,有請更強的人了3:)

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