题目描述

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

题解1：动态规划
当n = 1， f(1) = 1 = 2^0; 当n = 2， f(2) = 2 = 2^1;
当n = 3， f(3) = 4 =2^2 = f(2)+f(1)+1;
当n = 4， f(4) = 8 =2^3 = f(3)+f(2)+f(1)+1;
当n > 2， f(n) = 2^(n-1) =f(n-1)+f(n-2) +···+ f(2)+f(1)+1;

代码

class Solution {
public:
    int jumpFloorII(int number) {
        //题解1：动态规划
        if(number <=2) return number;
        int a = 1;
        int b = 2;
        int sum = a * b;
        for(int i =2;i<number;i++){
            sum<<2;//sum = sum * 2
        }
        return sum;
    }
};

题解2：数学规律
当n = 1， f(1) = 1 = 2^0; 当n = 2， f(2) = 2 = 2^1;
当n = 3， f(3) = 4 =2^2 = f(2)+f(1)+1;
当n = 4， f(4) = 8 =2^3 = f(3)+f(2)+f(1)+1;
当n > 2， f(n) = 2^(n-1) =f(n-1)+f(n-2) +···+ f(2)+f(1)+1;

代码

class Solution {
public:
    int jumpFloorII(int number) {
        //题解2：规律
        if(number == 0) return 0;//可忽略，题目中n>=0
        return pow(2, number-1);
    }
};