【7】变态跳台阶

题目描述

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

我的想法

因为和斐波那契变种的跳台阶很像，首先想到的还是写递归公式，看能不能推出什么。表面上有种f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n - (n-1))的感觉，发现如果真的是这样，完全可以化简成f(n) = 2^(n-2) * f(1)，但是这当然是错的，细细一想就会发现会多出很多重复情况，这个式子完全不可取。
于是换一种思路，可以去选择台阶，选择跳上n阶所踩过的台阶。于是得出这样的式子，f(n) = 1 + C(1, n-1) + C(2, n-2) + ... + C(n-1, n-1)，这很数学。列出阶乘公式，带入很容易就ac了。
代码如下：

public class Solution {
    public int JumpFloorII(int target) {
        int rtn = 1;
        long njie = jiecheng(target - 1);
        for (int i = 1; i < target; i++) {
            rtn += njie / (jiecheng(i) * jiecheng(target - 1 - i));
        }
        return rtn;
    }

    public long jiecheng(int start) {
        long rtn = 1;
        for (int i = start; i >= 1; i--) {
            rtn *= i;
        }
        return rtn;
    }
}

别人的思路

看到解析第一个，又惊了，只有几行代码......思路和我的很不一样，具体是这样的：
f(1) = f(1-1) = 1
f(2) = f(2-1) + f(2-2) = f(1) + f(0)
f(3) = f(3-1) + f(3-2) + f(3-3) = f(2) + f(1) + f(0)
f(n) = f(n-1) + f(n-2) + ... + f(n-n) = f(0) + f(1) + f(2) + ... + f(n-1)
解释一下就是当跳的台阶只有一阶时，只有一种跳法。
当跳两阶台阶时，可以分两种方式，直接跳上去，另一种是先跳一阶，再跳上去，只是第二种方法跳过第一步后就变成跳一阶的情况。
了。
同样跳三阶楼梯，分三种，1.先跳一阶后转换成f(2)，2.先跳两阶转换成f(1)，3.直接跳上去。
这种思路就推出了上面的公式。化简一下：
f(n-1) = f(0) + f(1) + f(2) + ... + f(n-2)
f(n) = (f(0) + f(1) + f(2) + ... + f(n-2)) + f(n-1) = 2*f(n-1)

推出来的公式真的超简单啊，代码就没有什么难度了
f(n) = 2*f(n-1)。

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
    }
}

但是毕竟这是递归，来看几个优化：
迭代：

class Solution {
    public int JumpFloorII(int target) {
        int rtn = 1;
        while (--target != 0) {
            rtn *= 2;
        }
        return rtn;
    }
}

位运算一行代码：

class Solution {
    public int JumpFloorII(int target) {
        return 1<<(target-1);
    }
}

可怕可怕，移位代替了乘2的工作，运算速度更快。
感觉自己想到方法已经很不容易了，看到别人的算法，感觉思维好有差距，还是要多练多练。