# 动态规划
# 斐波那契数列
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)
显然这是一个线性递推数列 (opens new window)。
- 时间复杂度 O(2 ^ n)
function fibo(n) {
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
return fibo(n - 1) + fibo(n - 2)
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 时间复杂度 O(n)
递归的思想，自上向下的解决问题
function fibo2(n) {
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
if (memo[n]) {
return memo[n];
}
return memo[n] = fibo2(n - 1) + fibo2(n - 2)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
动态规划核心：
将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终得到原问题的答案。
自下向上解决问题。
- 使用动态规划的思想
时间复杂度 O(n)
var memo = {};
function fibo(n) {
memo[0] = 0;
memo[1] = 1;
// debugger
for (var i = 2; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
// debugger
return memo[n];
}
console.log(fibo(20))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14