[每日一题]DP小结一：重叠子问题

本质上，就是在求解的过程中有重复计算。下图表示的求 斐波拉契数列的第 5 个元素的值。假设 f(n) 表示 斐波拉契数列第 n 个元素的值，那么 f(5) = f(5-1) + f(5-2) = f(4) + f(3)， f(4) = f(3) + f(2)  其中 f(3) 计算了两次。也就是说在求 f(5) 的过程中，至少有一个重复的计算 f(3) ，而f(3) 的求解就是全局解的重叠子问题。

重复计算的解题方案有两个：

1. 自顶向下的记忆优化

2. 自底向上的表格方案
   

自顶向下的记忆优化

先看一下纯的 DFS 的解法

记忆优化是基于 DFS版本来做的：在 DFS 的基础上，缓存下节点的值。

在第一次深度遍历的时候，我们把遍历的每次结果都缓存到起来（可以用数组或者Hash存储缓存）。在第二次遍历的时候，就不需要重复计算，直接在缓存中取结果就可以了。这样有效的降低算法的时间复杂度。

自底向上的表格方案
该方案就是从叶子节开始求解，并且用一个 Table 缓存下所有的求解的值。

先求 f(1) 得值，然后求 f(2) , f(3) ... f(n) ，并在求解的过程中，将f(x) 的值缓存到一个 数组或者表格中。

上面的解题方案的空间复杂度是 O(N) ，其中大部分空间都是浪费的。因为 n 的值至于 n - 1 和 n - 2 相关，其中 1 到 n - 3 的值不需要一直保存着。所以，本解题方案还可以继续优化：通过滚动数组的技巧将空间复杂度减少到O(1)。