它将一个问题分解成互相重叠的子问题，通过反复求解子问题，来解决原来问题
leetcode(509)斐波那契数列
- 定义子问题F(n) = F(n-1) + F(n-2)
- 反复执行从2循环到n ```javascript // 普通循环 function fibonacci(n){ var res1 = 1; var res2 = 1; var sum = res2; for(var i = 1;i < n;i ++){ sum = res1 + res2; res1 = res2; res2 = sum; } return sum; }
// 普通递归，有重复计算的性能问题 function fibonacci(n){ if(n==0)return 0 else if(n==1)return 1 else return fibonacci(n-1) + fibonacci(n-2) }
// 递归优化 /**
- @param {number} n
- @return {number}
*/
var fib = function(n) {
if(n < 2) return n
const d = [0, 1]
for(let i = 2; i <= n; i++) {
} return d[n] }; ```d[i] = d[i-1] + d[i-2]
leetcode(70)爬楼梯
爬到第n阶可以再第n-1阶爬1个台阶，或者再n-1阶爬2个台阶
F(n) = F(n-1) + F(n-2)
时间复杂度： O(n)
若有收获，就点个赞吧
0 人点赞
