題目描述

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。

示例 1：

輸入：n = 2
輸出：2
示例 2：

輸入：n = 7
輸出：21
提示：

0 <= n <= 100

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

解題思路

自頂向下分析，由于一次只能跳1級(jí)臺(tái)階或者2級(jí)臺(tái)階，因此青蛙跳到第n級(jí)之前要么在第n-1級(jí)臺(tái)階上，要么在第n-2級(jí)臺(tái)階上，若跳上n級(jí)臺(tái)階的跳法為f(n)，則f(n) = f(n-1) + f(n-2)；
自底向上分析，只有1級(jí)臺(tái)階時(shí)，有1種跳法；有2級(jí)臺(tái)階時(shí)，有2種跳法（2次各跳1級(jí)，一次跳2級(jí)）；有3級(jí)臺(tái)階時(shí)，有3種跳法（從第1級(jí)跳2級(jí)直接到第3級(jí)，從第2級(jí)跳1級(jí)到第3級(jí)）；以此類推......這就是斐波那契數(shù)列的應(yīng)用。

代碼

int numWays(int n){
    int simp_ways[2] = {1, 1};
    int waysn = 0, way1 = 1, way2 = 1;

    if(n < 2)
    {
        return simp_ways[n];
    }

    for (int i = 2; i <= n; i++)
    {
        waysn = (way1 + way2) % 1000000007;
        way1 = way2;
        way2 = waysn;
    }

    return waysn;
}

測(cè)試代碼及結(jié)果

#include<stdio.h>

int main(void)
{
    // 功能測(cè)試
    printf("n = 5: %d\n", numWays(5));
    printf("n = 10: %d\n", numWays(10));

    // 邊界值測(cè)試
    printf("n = 0: %d\n", numWays(0));
    printf("n = 1: %d\n", numWays(1));
    printf("n = 2: %d\n", numWays(2));

    // 性能測(cè)試
    printf("n = 2: %d\n", numWays(50));
    printf("n = 2: %d\n", numWays(100));
}

執(zhí)行結(jié)果

時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)。