# 题目

509. 斐波那契数

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

• 示例 1：
输入：2



0 <= n <= 30

# 思路1-递归

public int fib(int n) {
if(n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}


Runtime: 6 ms, faster than 30.76% of Java online submissions for Fibonacci Number.
Memory Usage: 35.9 MB, less than 37.14% of Java online submissions for Fibonacci Number.


# 思路2-动态规划

## 思路分析

（1）初始化条件

dp[0] = 0;
dp[1] = 1;


（2）递推公式

dp[n] = dp[n-1] + dp[n-2]


## java 实现

java 实现起来也不难。

public int fib(int n) {
if(n <= 1) {
return n;
}

int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}


### 效果

Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 35.9 MB, less than 37.14% of Java online submissions for Fibonacci Number.


## 时间复杂度优化

### 滚动数组

dp[n] = dp[n-1] + dp[n-2]


### java 实现

public static int fib(int n) {
if(n <= 1) {
return n;
}
int pre = 0;
int current = 1;
for(int i = 2; i <= n; i++) {
int temp = current;
current = pre + current;
pre = temp;
}
return current;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 35.7 MB, less than 65.02% of Java online submissions for Fibonacci Number.


# 思路3-拓展篇

## 矩阵-O(logn) 复杂度

《剑指 Offer》 中也提到了这个不是很实用的解法，是一个矩阵，感兴趣的可以查一下。

## 递推公式

### java 实现

private static final double FAC_ONE = 1 / Math.sqrt(5);
private static final double FAC_TWO = 0.5 + Math.sqrt(5) / 2;
private static final double FAC_THREE = 0.5 - Math.sqrt(5) / 2;

public static int fib(int n) {
if(n <= 1) {
return n;
}
return (int) (FAC_ONE * (Math.pow(FAC_TWO, n) - Math.pow(FAC_THREE, n)));
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 35.6 MB, less than 65.02% of Java online submissions for Fibonacci Number.


# 思路4-空间换时间

## 空间换时间

private static final int[] nums = new int[]{
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
};

public static int fib(int n) {
return nums[n];
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 35.8 MB, less than 37.14% of Java online submissions for Fibonacci Number.


# 爬楼梯问题

## 题目

• 示例 1：
输入： 2

1.  1 阶 + 1 阶
2.  2 阶


## 思路

// 如果为1，只有1中
// 如果为2，则有 11 或者 2
// 如果为3  111 12 21
// 如果为4  1111 112 121 211 22
// 有两种方式：第一次走一步；第一次走两步。


dp[i] = dp[i-1] + dp[i-2];


## java 实现

public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.
Memory Usage: 35.4 MB, less than 91.67% of Java online submissions for Climbing Stairs.


## 滚动数组优化

public int climbStairs(int n) {
int pre = 1;
if(n <= 1) {
return pre;
}
int current = 2;
for(int i = 2; i < n; i++) {
int temp = current;
current += pre;
pre = temp;
}
return current;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.
Memory Usage: 35.6 MB, less than 71.64% of Java online submissions for Climbing Stairs.


# 拓展阅读

1. decode ways
1. Unique Paths
1. Climbing Stairs
1. Fibonacci Number

# 参考资料

https://leetcode-cn.com/problems/climbing-stairs/