題目：
?
給定整數(shù)N，代表臺(tái)階數(shù)，一次可以跨2個(gè)或者1個(gè)臺(tái)階，返回有多少種走法。
舉例：
N=3，可以三次跨一個(gè)臺(tái)階，也可以先跨2再跨1，也可以先跨1再跨2，共三種走法。
思路：
如果臺(tái)階只有1級(jí)，方法只有一種，如果臺(tái)階有兩級(jí)，方法有兩種。如果臺(tái)階有N級(jí)，最后跳上第N級(jí)臺(tái)階時(shí)，要么從N-2級(jí)臺(tái)階直接跨2級(jí)，要么從N-1級(jí)跨1級(jí)上去。所以臺(tái)階有N階的方法為跨到N-2級(jí)臺(tái)階的方法數(shù)加上跨到N-1級(jí)臺(tái)階的方法數(shù)。即S(N)=S(N-1)+S(N-2)
?S(1)=1 S(2)=2 。
例如臺(tái)階為5階：（共八種）
先跨3階，1 1 1，1 2， 2 1，最后一步跨 2（共三種）
先跨4階，1 1 1 1，1 1 2，1 2 1，2 1 1 ，2 2，最后一步跨1（共五種）
類似于斐波那契數(shù)列：
方法一: 暴力遞歸
public static int s1(int N) {
if (N == 1) {
return 1;
}
if (N == 2) {
return 2;
}
return s1(N-1) + s1(N-2);
}方法二：O(N)
public static int s2(int N) {
if (N < 1) {
return 0;
}
if (N == 1 || N ==2) {
return N;
}
int res = 2;
int pre = 1;
int tmp = 0;
for (int i = 3; i <= N; i++) {
tmp = res;
res += pre;
pre = tmp;
}
return res;
}方法三：（使用矩陣乘法）
S(N)=S(N-1)+S(N-2)是一個(gè)二階遞推數(shù)列，用上篇博客的矩陣乘法的方法，根據(jù)前四項(xiàng)
?代碼實(shí)現(xiàn)：文章來源：http://www.zghlxwxcb.cn/news/detail-439295.html
代碼中的matrixPower方法在這篇博客介紹：斐波那契數(shù)列問題文章來源地址http://www.zghlxwxcb.cn/news/detail-439295.html
public static int s3(int N) {
if (N < 1) {
return 0;
}
if (N == 1 || N ==2) {
return N;
}
int[][] base = {{1,1},{1,0}};
int[][] res = matrixPower(base, N-2);
return 2*res[0][0] + res[1][0];
}到了這里，關(guān)于斐波那契問題——上臺(tái)階問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
