08 跳台阶

题目描述

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

思路：

本题为斐波那契数列的变形，思路参考上题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int jumpFloor(int number) {
        int first=1,second=2;
        if(number==1)return 1;
        if(number==2)return 2;
        int current=0;
        for(int i=3;i<=number;i++){
            current=first+second;
            first=second;
            second=current;
        }
        return current;
    }
};

09 变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：

跳上n级台阶，等于跳上n-1台阶方法的和+1

f(n)=f(n-1)+f(n-2)+f(n-3)……+f(1)+1

f(n-1)=f(n-2)+f(n-3)……+f(1)+1

可推导出

f(n)=f(n-1)*2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int jumpFloorII(int number) {
        vector<int> a(number+1,0);
        a[1]=1;
        a[2]=2;
        for(int i=3;i<=number;i++){
            a[i]=a[i-1]*2;
        }
        return a[number];
    }
};

10 矩形覆盖

题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

image-20210222185805944

思路：

依旧是斐波那契数列的一个变型

image-20210222190205246

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rectCover(int number) {
        if(number<=2)return number;
        int a=1,b=2,c;
        for(int i=3;i<=number;i++){
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};