面试题9：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
Basic ：斐波那契数列定义
当 0 < n <= 1 时，f(n) = n;
当 n > 1 时，f(n) = f(n-1) + f(n-2)
解题思路
一、递归写法（低效，慢）
递归分析，如下图所示：
这棵树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味计算量会随着n的增大而急剧增大。
用递归方法计算的时间复杂度是以n的指数的方式递增的。
二、for 循环写法
使用中间变量，在每次循环之后都将中间计算结果保存起来，用于下一次循环，时间复杂度减少到O(n)。
代码实现
一、递归写法（低效，慢）
public class Solution {
public int Fibonacci(int n) {
if(n <= 1) {
return n;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
二、for 循环写法
public class Solution {
public int Fibonacci(int n) {
if(n <= 1) {
return n;
}
int fibNMinus1 = 1;
int fibNMinus2 = 0;
int fibN = 0;
for(int i=2; i<=n; i++){
fibN = fibNMinus1 + fibNMinus2;
fibNMinus2 = fibNMinus1;
fibNMinus1 = fibN;
}
return fibN;
}
}
总结
递归实现起来简洁，但通常效率比for循环要低很多。
扩展：青蛙跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路分析
前提只有 一次 1阶或者2阶的跳法。
a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a和b 两种假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.Base case：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
public class Solution {
public int JumpFloor(int target) {
if(target <= 0) {
return -1;
}
if(target <= 2){
return target;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
数学归纳法，各种计算，略过。
题目：我们可以用2×1（图2.13的左边）的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形（图2.13的右边），总共有多少种方法？
思路分析
首先把 2x8 的覆盖方法总数记为 f(8)。
用第一个 1x2 小矩形去覆盖大矩形的最左边时有两个情形，竖着放或者横着放。
竖着放：右边还剩下 2x7 的区域，这种情形下的覆盖方法记为 f(7)。
横着放：1x2 小矩形不管是横着放在左上角还是左下角，另外一个小矩形必须跟在该小矩形的下边或上边贴合，即无论如何只有
一种覆盖方法。而此时右边还剩下 2x6 的区域，这种情形下的覆盖方法记为 f(6)。
2x8 的覆盖方法就由这两种情形构成，因此，他们之间存在以下关系：
f(8) = f(7) + f(6)
类推：f(n) = f(n-1) + f(n-2) 即斐波那契数列。
代码实现
public class Solution {
public int RectCover(int target) {
if(target<=2) {
return target;
}
return RectCover(target - 1) + RectCover(target - 2);
}
}
leetcode 70. 爬楼梯
题目链接
解法1：暴力递归
不通过：超出时间限制，这种解法的时间复杂度是指数级。
在n大的时候，递归栈非常之深，每次去递归时间开销很大，所以会抛出超时。
解法2：动态规划
public int climbStairs(int n) {
if(n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
动态规划通过申请一个数组保存所有的状态量，避免了重复计算，将时间复杂度优化到 O(n)，由于开辟了一个长度为 n+1 的数组，因此空间复杂度为 O(n)。
解法3：保留中间项
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++) {
int third = first + second; //每次计算都是以上次计算结果为基础
first = second;
second = third;
}
return second;
}
我们其实不需要保存所有中间状态量，只需要三个变量来保存所需的前两个中间项即可，这样进一步优化了空间复杂度到 O(1)。
保留中间计算结果的方式减少了重复计算，每次计算都是以上次计算结果为基础。 时间复杂度是O(n)，空间复杂度是 O(1)
