7. 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
思路： 初始化f=0，g=1，f为第n项数列的值，g为第n+1项数列的值。循环n次，令g=g+f，f=g-f，利用后一项推出前一项，减少存储，复杂度为O(n)。
1
2
3
4
5
6
7
8
9
10
public class Solution {
public int Fibonacci(int n) {
int f = 0, g = 1;
for(int i = 0; i < n; i++){
g += f;
f = g - f;
}
return f;
}
}
8. 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路： 变种斐波那契数列，青蛙每次能跳1阶或者2阶台阶，则跳第n阶时，可以从第n-1阶或者n-2阶跳上来，次数为跳第n-1阶的次数加上第n-2阶的次数。另一种思路是跳n阶台阶是1和2的一种组合，令总的跳1阶的次数为x，跳2阶的次数为y，n = x+2y，总跳法数为C（x+y）取 y次，y范围为[0, n/2]。
1
2
3
4
5
6
7
8
9
10
public class Solution {
public int JumpFloor(int target) {
int f=1, g=2;
for(int i=1; i<target; i++){
g += f;
f = g - f;
}
return f;
}
}
9. 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路： 尝试一下列出跳台阶次数，发现是一个等比数列，1 2 4 8……。
根据上一题斐波那契数列的思路，跳第n阶可以从前面n-1阶中的任意一阶跳上来，
即f(n) = f(n-1) + f(n-2) …… + f(1)，其中第一项f(n-1) = f(n-2) + f(n-3) …… + f(1)，得f(n) = 2*f(n-1)，可知总跳法数为公比为2的等比数列。
1
2
3
4
5
public class Solution {
public int JumpFloorII(int target) {
return 1<<(target - 1);
}
}
10. 矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路： 一样是斐波那契数列的变种，因为大矩形宽度为2，因此无论怎么放，大矩形都是上下对称的，只看上一半，就是每次填一个或者两格，和青蛙跳台阶是一样的，数列为0 1 2 3 5 8……注意一点是，这次题目包含的 n=0的情况，当n=0时返回0即可。
1
2
3
4
5
6
7
8
9
10
public class Solution {
public int RectCover(int target) {
int f = (target >= 1)? 1: 0, g = 2;
for(int i = 1; i < target; i++){
g += f;
f = g - f;
}
return f;
}
}