名企筆試：京東 2016 算法工程師筆試題（登樓梯）

有一段樓梯臺階有 15 級臺階，以小明的腳力一步最多只能跨 3 級，請問小明登上這段樓梯，有多少種不同的走法?

A. 2345

B. 3261

C. 5768

D. 6843

思路：  一道遞推題。定義F(x)表示到達第x級臺階的走法總數(shù)。可以從x-3級臺階走三步直接到達x，也可以從x-2走兩步直接到達x，還可以從x-1走一步到達x，所以F(x) = F(x-1) + F(x-2) + F(x-3).

初始化邊界：

F(0) = 1; F(1) = 1; F(2) = 2; F(3) =F(0) + F(1) + F(2);

.....

一直遞推即可得到答案 F(15) = 5768。

代碼:

#include<cstdio>const int maxn = 20;int ans[maxn];void solve(){    ans[0] = 1;    ans[1] = 1;    ans[2] = 2;    for(int i = 3; i < 20; ++i){        ans[i] = ans[i-1] + ans[i-2] + ans[i-3];    }}int main(){    solve();    PRintf("%d/n",ans[15]);    return 0;}如有不當之處歡迎指出！