动态规划入门：斐波那契数列与递归优化

第三章 动态规划算法（上） 本章主要探讨了动态规划在解决特定问题中的应用，以斐波纳契数列为例进行问题引入。斐波纳契数列是一个经典的递归问题，其定义为F(n) = F(n-1) + F(n-2)，当n等于0或1时，结果为1。传统递归实现的代码如`int Fibonacci(int n)`中，存在大量重复计算的问题，例如在计算F(5)时，会计算F(3)和F(2)两次。 动态规划是一种解决这类问题的有效方法，它通过避免重复计算来提高效率。核心思想是将原问题分解为子问题，并通过存储子问题的解（例如，使用数组f[i]存储Fibonacci序列的前n项）来构建解决方案。在这个例子中，`int Fibonacci(int *f, int n)`版本的函数，利用数组存储已经计算过的值，从而达到时间复杂度为O(n)，显著降低了计算量。 动态规划方法概要包括以下步骤： 1. **问题的递归表示**：原问题的解可以通过子问题的解组合得到，如F(n)。 2. **存储子问题解**：使用表格（数组）存储子问题的解，避免重复计算。 3. **自底向上计算**：从最小子问题开始，逐步填充表格，遇到已知答案则直接使用，不重新计算。 4. **最优子结构**：动态规划问题通常具有最优子结构性质，即最优解由其子问题的最优解构成。 接下来，章节转向了矩阵连乘问题，这是一个更复杂的优化问题。矩阵连乘的目标是找到n个矩阵A1、A2…An的最优计算次序，使得总的计算量最小。动态规划同样适用于此问题，通过分析最优解的结构，发现最优子结构的存在，即计算矩阵Ai..j的最优顺序包含了其子问题Ai..k和Ak+1..j的最优顺序。动态规划通过自底向上的策略求解这个问题，找出最小化总计算量的矩阵链分解。 总结来说，本章通过斐波纳契数列和矩阵连乘问题，深入介绍了动态规划的基本思想、应用对象、解决问题的步骤以及如何利用最优子结构性质来解决重复计算问题。动态规划是计算机科学中一种强大的工具，对于优化复杂问题和减少计算负担有着重要意义。