第一题 斐波那契数列
一种是递归方法，也就是fib[i]=fib[i-1]+fib[i-2]，此时fib是一个大小是n+1的数组，初始化时候是int[] fib = new int[n+1];然后不停循环递归算值
一种是动态规划方法缓存，从fib = 0+1 缓存至fib=pre2+pre1。还是比较简单的
package com.lyc.dataautest;
public class Fibonacci {
public static int fibno(int n) {
if(n<2) return n;
int pre0=0;
int pre1=1;
int rs=0;
for(int i=2;i<n+1;i++) {
rs=pre0+pre1;
pre0 = pre1;
pre1 = rs;
}
System.out.println("n is:"+rs);
return rs;
}
public static void main(String[] args) {
fibno(6);
}
}
每次拷贝到<号的时候都拷贝失败，简书的bug就是这里了。
第二题 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法、
只青蛙一次可以跳上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)
当n = 4时，f(4) = f(3) +f(2),以此类推...........可以联想到Fibonacci数列
第三题 变态跳台阶、
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。interview上的解法不够清晰抛弃；
算法解决参考https://www.cnblogs.com/purehol/p/8087319.html
关于本题，前提是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);
...
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)
接下来就可以写代码了，参考作者purehol的方法，是搜索出来最容易理解，干净的两个方法
方法1 参考上述算法
方法2 乘法不如二进制移位快，这样就可以了：
public class BtFrogjump {
public static int btjump1(int n) {
return 1<<--n;
}
public static int btjump(int n) {
if(n<2) return n;
int pre = 1;
for(int i=2;i<n+1;i++) {
pre = 2*pre;
}
return pre;
}
public static void main(String[] args) {
int result = btjump1(7);
System.out.println("the result:"+result);
}
}
