剑指Offer——变态跳台阶

By AverageJoeWang
 标签:

变态跳台阶

  • 题目描述

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

  • 解题思路

    • n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;
    • n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2) = 2;
    • 到这里为止,和普通跳台阶是一样的。
    • n = 3 时,有三种跳的方式,第一次跳出一阶后,对应Fib(3-1)种跳法; 第一次跳出二阶后,对应Fib(3-2)种跳法;第一次跳出三阶后,只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
    • 当n = 4时,有四种方式:第一次跳出一阶,对应Fib(4-1)种跳法;第一次跳出二阶,对应Fib(4-2)种跳法;第一次跳出三阶,对应Fib(4-3)种跳法;第一次跳出四阶,只有这一种跳法。所以,Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4)种跳法。
    • n = n 时,共有n种跳的方式,第一次跳出一阶后,后面还有Fib(n-1)中跳法; 第一次跳出二阶后,后面还有Fib(n-2)中跳法.第一次跳出n阶后,后面还有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)
    • 同样根据思路,可以得到
    • f(n)=f(n-1)+f(n-2)+....+f(1)+1
    • f(n-1)=f(n-2)+....+f(1)+1
    • 两个式子相减,得到f(n) = 2f(n-1),n>3
  • 代码实现
public class Solution {
    public int JumpFloorII(int target) {
         int count[] = new int[101];
        count[0] = 1;
        count[1] = 1;
        count[2] = 2;
        int index = 2;
        if (target <= index) return count[target];
        if (target > 100) target = 100;
        for (int i = index + 1; i <= target; i++){
            count[i] = 2*count[i-1];
        }
        index = target;
        return count[index];
    }
}