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阶的跳法。
-
由以上可知：
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);
-
可以知道有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),不再实现，注意边界值就行
