斐波那契数列
以斐波那契数列 (opens in a new tab)为例，讲解动态规划的思想。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列的自上而下，使用递归实现，在假设已经求得上面的值的情况下，可以很容易的求得下面的值，但是这种实现方式会有很多重复计算，比如求 F(5) 的时候，需要先求 F(4) 和 F(3)，但是求 F(4) 的时候，又需要先求 F(3) 和 F(2)，这样就会重复计算 F(3)。这种实现方式我们需要保存已经计算过的值，这样就可以避免重复计算。
function fib(n: number): number {
const mod = 1000000007;
// 自上而下，递归
const memo = new Map();
function dp(n: number): number {
// base case
if (n < 2) {
return n;
}
// 去重
const memoValue = memo.get(n);
if (memoValue !== undefined) {
return memoValue;
}
const res = (dp(n - 1) + dp(n - 2)) % mod;
memo.set(n, res);
return res;
}
return dp(n);
}因为自上而下是递归，空间复杂度比较高，所以我们可以更进一步使用自下而上使用迭代的方式，从下面的值开始计算，这样还能避免重复计算。
function fib(n: number): number {
const mod = 1000000007;
// 自下而上，迭代
const dp = new Array(n);
// base case
dp[0] = 0;
dp[1] = 1;
// -------
for (let i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
}
return dp[n];
}上面例子的空间复杂度还能更进一步优化，因为我们只需要保存 dp[i-1] 和 dp[i-2]，所以我们可以只使用两个变量来保存。下面就是我们经常看到的题解了。
function fib(n: number): number {
const mod = 1000000007;
// 自下而上，迭代，滚动窗口
if (n < 2) return n;
// 分别代表上面的 dp[i-1] 和 dp[i-2]
let dp1 = 1,
dp2 = 0;
for (let i = 2; i <= n; i++) {
const dp_i = (dp1 + dp2) % mod;
dp2 = dp1;
dp1 = dp_i;
}
return dp1;
}