动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i] 的含义为 第 i 个数的斐波那契数值是 dp[i]；
确定递推公式：状态转移方程
dp[i] = dp[i - 1] + dp[i - 2]；如何初始化 dp 数组：题干初始化了 dp 数组
dp[0] = 0；dp[1] = 1；确定遍历顺序：根据递推公式得知，dp[i] 为前面 dp[i - 1]、dp[i - 2] 的和，所以是从前向后遍历；
举例推导 dp 数组：
第 i 项索引 0 1 2 3 4 5 6 7 8 9 10 … 第 i 项的斐波那契数值 dp[i] 0 1 1 2 3 5 8 13 21 34 55…
复杂度
-
时间复杂度：
O(2^n)，子问题个数，即递归树中节点的总数； -
空间复杂度：
O(n)；
代码实现
JavaScript
JavaScript
// 循环实现
var fib = function (n) {
let dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
// 递归实现
var fib = function (n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
};
动态规划（状态压缩）
解题思路
上面的暴力递归，造成了时间和空间的浪费，例如：
f(20) = f(19) + f(18)
想要计算原问题 f(20) 就得先计算出子问题 f(19) 和 f(18) ，然后要计算 f(19) 就要先算出子问题 f(18) 和 f(17) ，以此类推；
首先计算子问题个数，即递归树中节点的总数，显然二叉树节点总数为指数级别，所以子问题个数为
O(2^n)；观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间；
可以利用 备忘录 将 重复的子问题 存储起来，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了；由于每一次的计算只需要前两项的结果，则可以存储前两项的结果即可；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
JavaScript
JavaScript
// 递归实现
var helper = function (memo, n) {
if (n < 2) return n;
// 备忘录
if (memo[n]) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n]
}
var fib = function (n) {
return helper([], n);
};
// 迭代实现
var fib = function (n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
let sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 912. 排序数组
上一篇
评论
