這是一個(gè)經(jīng)典的遞歸問(wèn)題.也就是費(fèi)波納西級(jí)數(shù).
f(n) = f(n-1) + f(n-2).
如果我們第一部選1個(gè)臺(tái)階,那么后面就會(huì)剩下n-1個(gè)臺(tái)階,也就是會(huì)有f(n-1)種走法.如果我們第一部選2個(gè)臺(tái)階,后面會(huì)有f(n-2)個(gè)臺(tái)階.因此,對(duì)于n個(gè)臺(tái)階來(lái)說(shuō),就會(huì)有f(n-1) + f(n-2)種走法.
因此,1個(gè)臺(tái)階f(1) = 1.
f(2) = 2,
f(3) = 3
f(4) = 5
f(5) = 8
f(6) = 13
f(7) = 21
f(8) = 34
f(9) = 55
f(10) = 89
f(11) = 89+55 = 144
f(12) = 144 + 89 = 233