斐波那契数列、跳台阶、矩形覆盖

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

int Fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }
    int a = 0;
    int b = 1;
    while (n--) {
        int c = a + b;
        a = b;
        b = c;
    }
    return a;
}

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

int jumpFloor(int number) {
    if (number <= 2) {
        return number;
    }
    int a = 1;
    int b = 2;
    for (int i = 3; i <= number; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

涂掉最后一级矩形的时候，是用什么方式完成的？

n = 1 的时候 只能横着覆盖，一种 n = 2 的时候 可以横着和竖着覆盖，两种 n = 3 的时候 第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法 第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法 总共有 3 种 n = 4 的时候 第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法 第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法 总共有 5 种方法 n = n 的时候 第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法 第 n 级竖着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法 总和为两种情况的总和

int rectCover(int number) {
    if (number <= 2) {
        return number;
    }
    int a = 1;
    int b = 2;
    for (int i = 3; i <= number; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}