简单理解动态规划

动态规划的核心思想就一句: 将问题拆分成更小的子问题并存储结果来避免重复计算。 也就是用空间换时间

从最经典的斐波那契数列来看动态规划：

斐波那契数列：从0和1开始，后续的每一项都是前两项的和

根据斐波那契数列的概念，直觉是可以通过递归得到计算结果

function fibonacci(n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);
}

我们按步骤分析代码执行顺序：

调用 fibonacci(4)→ fibonacci(3) + fibonacci(2)
调用 fibonacci(3)→ fibonacci(2) + fibonacci(1)
调用 fibonacci(2)→ fibonacci(1) + fibonacci(0)
fibonacci(1) 返回 1
fibonacci(0) 返回 0
所以 fibonacci(2) 返回 1
回到 fibonacci(3)：fibonacci(3) = fibonacci(2) + fibonacci(1)
= 1 + 1 = 2
回到 fibonacci(4)：现在计算 fibonacci(2)（这是之前的结果，我们需要再次计算）：
→ fibonacci(1) + fibonacci(0)
fibonacci(1) 返回 1
fibonacci(0) 返回 0
所以 fibonacci(2) 返回 1。
最后，合并结果：fibonacci(4) = fibonacci(3) + fibonacci(2)
= 2 + 1 = 3
因此，调用 fibonacci(4) 返回 3

该算法的时间复杂度为O(2^n)，耗费的时间极长，我们分析代码可以发现，递归过程中，其中许多值（如 fibonacci(2)）被多次计算，我们把计算过程产生的结果存储起来，不就可以提高我们算法的效率吗！

优化后的代码如下：

function fibonacci(n) {if (n < 2) {return n}const prev = [0, 1]for (let i = 2; i <= n; i++) {prev[0] = prev[1]prev[1] = prev[0] + prev[1]}return prev[1]
}

我们只需要把数列的最后两个值存储起来，避免不必要的计算，就可以把时间复杂度降低到O(n)，这个就是动态规划的核心思想。

但并不是所有问题都适合动态规划，判断一个问题是否适合使用动态规划解决，通常可以沿着以下几个步骤进行分析：

1. 是否可以分解成子问题？子问题是否重复出现
2. 最优解是否依赖于子问题的最优解
3. 怎么定义问题的解决步骤
4. 确定边界条件
5. 分析问题的规模，以确保通过动态规划可以在合理的时间内解决它。