Description

有一座樓梯共有 n 階，小明從第 0 階開始，每次可以選擇走 1 階、走 2 階或走 3 階。

請撰寫一個程式，使用遞迴方法計算小明走到第 n 階，總共有幾種不同的走法。

要走到第 n 階，最後一步只可能是：

• 從第 n-1 階走 1 階上來
• 從第 n-2 階走 2 階上來
• 從第 n-3 階走 3 階上來
• 提示： f(0)=1, f(1)=1, f(2)=2, f(3)=4, f(4)=7, f(5)=13, f(6)=24, f(7)=44, f(8)=81, f(9)=149, f(10)=274

Requirements

輸入：

• 一個整數 n。

輸出:

• 輸出一個整數，表示總共有幾種不同的走法。

Input / Output