c547: Bert 爬樓梯

內容

BERT 是個奇怪的人，爬樓梯都不乖乖乖的一次走一格，而是有時走一階，或一次走兩階。
換句話說，假設階梯有三階，那他有三種走法
一： 第一步走一階，第二步走二階。
二： 第一步走二階，第二步走一階。
三： 全程都走一階。

現在請你寫個程式，算出如果是 n 格樓梯，Bert 有幾種走法 ?

輸入

多筆輸入

每行一個數字 N ，代表現在有 N 階樓梯 。

(1 <= Ｎ <= 10000)

3
1

輸出

每行一個數字，代表當樓梯有 N 階時答案。

答案可能很大，請 mod 1000000007

3
1

解題思路

DP 題，看起來有三種可能，但實際上只需考慮走 1 步和走 2 步兩種情況。

而因為只能走兩步，所以如果你想要走到第 n 階，你只有從 n-1 階走一步和 n-2 階走兩步兩種情況需要考慮。也就是說走到第 n 階的可能性就是 n-1 階和 n-2 階的可能性相加。

所以整理出公式

if n <= 1 , s[n] = 1
if n >= 2 , s[n] = s[n-1] + s[n+2]

完整程式碼

AC (4ms, 124KB)

#include <stdio.h>
#define Mod 1000000007

int list[10001] = { 1, 1 };

int main()
{
    int n;
    for (int i = 2; i <= 10000; i++)
        list[i] = (list[i - 1] + list[i - 2]) % Mod;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", list[n]);
    }
    return 0;
}