动态规划算法：递归树与矩阵连乘优化

第三章内容主要探讨了动态规划算法在解决递归问题中的应用，以斐波纳契数列为例进行深入讲解。首先，引入了递归方法来计算斐波纳契数列，通过`Fibonacci`函数，每个数`F(n)`被递归地定义为前两个数之和，导致了大量重复计算，例如在计算`F(5)`时，递归树清晰地展示了这一现象： ``` F(5) = F(4) + F(3) F(4) = F(3) + F(2) F(3) = F(2) + F(1) ... F(2) = F(1) + F(0) ``` 递归方法的时间复杂度为O(2^n)，效率较低。 接着，引入了动态规划来优化这个问题。动态规划是一种通过将原问题分解为相互重叠的子问题，存储子问题的解来避免重复计算的技术。在`Fibonacci`的动态规划版本中，我们使用一个数组`f`来存储已经计算过的斐波那契数，从而达到O(n)的时间复杂度，减少了重复计算： ```c++ int Fibonacci(int* f, int n) { f[0] = f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; } ``` 动态规划的基本步骤包括： 1. 分析原问题的最优子结构，即问题的最优解依赖于其子问题的最优解。 2. 定义递归关系，如斐波那契数列的`F(n) = F(n-1) + F(n-2)`。 3. 自底向上填充表格，从最小的子问题开始计算并存储结果。 4. 当遇到已计算的子问题时，利用存储的结果，而不是重新计算，节省计算时间。 接下来，章节还扩展到了矩阵连乘问题，这是一个具有最优子结构的典型动态规划问题。在这个场景中，目标是找到一系列矩阵的连乘顺序，使得总的计算量最小。动态规划同样被用来分析子问题的最优解，通过分治策略，将大问题分解为小问题，逐步构建出全局最优解。 总结来说，本章的核心知识点包括递归与动态规划的区别，如何通过动态规划优化递归算法，以及动态规划在解决具有最优子结构问题中的应用，如斐波纳契数列和矩阵连乘问题。通过理解这些概念和方法，可以有效地提高算法效率并解决复杂问题。