剑指offer-JZ28-跳台阶 JZ10-矩形覆盖

题目描述

JZ28:一只青蛙一次能够跳上1级台阶，也能够跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（前后次序不一样算不一样的结果）。code

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

思路：class

JZ28:找规律，f(n)为跳上n级台阶跳法，不难发现 f(1) = 1,f(2) =2 ,f(3)=f(1)(先跳2阶，剩下一阶)+f(2)(先跳一阶，剩下两阶)，..即f(n) = f(n-1)+f(n-2),f(n)为斐波那契数列，解法同JZ 27方法

JZ10:找规律法相似于JZ28co

C++return

class Solution {
public:
    int jumpFloor(int number) {
        //f(n) = f(n-1) + f(n-2)
        if(number < 1)
            return 0;
        vector<int> dp(number+1);
        dp[1] = 1, dp[2] = 2;
        for(int i = 3; i <= number; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
    }
};