Java日记2018-05-27

10.1 斐波那契数列
for循环的n大小比较易错

public class Solution0527 {
    public static int Fibonacci(int n) {
        if(n<2) return n;
        int pre=0;
        int f1=0;
        int f2=1;
        for(int i=2;i<n;i++) {
            pre =f2+f1;
            f1=f2;
            f2=pre;
        }
        System.out.println(pre);
        return pre;
    }
    public static void main(String[] args) {
        Fibonacci(3);
        Fibonacci(4);
    }

}

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

首先考虑n等于0、1、2时的特殊情况，f(0) = 0 f(1) = 1f(2) = 2
其次，当n=3时，青蛙的第一跳有两种情况：跳1级台阶或者跳两级台阶

假如跳一级，那么 剩下的两级台阶就是f(2)；假如跳两级，那么剩下的一级台阶就是f(1)，因此f(3)=f(2)+f(1)

其实就是公式的现实版

10.3 变态跳台阶

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

首先是算法，公式完全记得，但是已经为啥不清楚了，再看一遍
关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(0) = 1;

f(1) = 1;

f(2) = f(2-1) + f(2-2); //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3);
Fib(0)肯定需要为0，否则没有意义。但是我们设定Fib(0) = 1 当n = 3 时，有三种跳的方式，第一次跳出一阶后，对应Fib(3-1)种跳法； 第一次跳出二阶后，对应Fib(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n);

说明：

1）这里的f(n) 代表的是n个台阶有1,2,...n阶的跳法。

2. 由以上可知：

   f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1);

   故f(n-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2);

   所以 f(n) = f(n-1) + f(n-1) = 2 * f(n-1);

3. 可以知道有n阶台阶，有1、2、...n阶的跳的方式时，总共跳法为：

            1              ,(n=0 )
   

f(n) = 1 ,(n=1 )

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

再具体实现上，因为看到了2的乘积，更优的算法是使用移位，另外一种就是按照公式算（参考原来日记记录）

public static int btjump1(int n) {
        return 1<<--n;
    }

10.4 矩形覆盖
画个图很容易理解又是fibonacci f(n) = f(n-1) + f(n-2),不再实现，注意边界值就行