一、題目

??三步問(wèn)題。有個(gè)小孩正在上樓梯，樓梯有n階臺(tái)階，小孩一次可以上1階、2階或3階。實(shí)現(xiàn)一種方法，計(jì)算小孩有多少種上樓梯的方式。結(jié)果可能很大，你需要對(duì)結(jié)果模1000000007。

示例1:

輸入： n = 3
輸出： 4
說(shuō)明: 有四種走法

示例2:

輸入： n = 5
輸出： 13

提示:

• n 范圍在 [1, 1000000] 之間

??點(diǎn)擊此處跳轉(zhuǎn)題目。

二、Java 題解

??比較簡(jiǎn)單，直接上代碼了。有點(diǎn)類似斐波那契數(shù)列。

class Solution {public int waysToStep(int n) {int ans = 4;int[] f = new int[] { 1, 2, 4 };if (n < 3) return f[n - 1];while (n > 3) {ans = ((f[0] + f[1]) % 1000000007 + f[2]) % 1000000007; f[0] = f[1];f[1] = f[2];f[2]= ans;n--;}return ans;}
}

• 時(shí)間：14 ms，擊敗 75.78% 使用 Java 的用戶
• 內(nèi)存：37.17 MB，擊敗 85.21% 使用 Java 的用戶