动态规划：消除冗余，构建最优解

"动态规划的基本思想-算法动态规划部分" 动态规划是一种强大的算法设计策略，主要用于解决最优化问题。它主要基于分治和消除冗余的原则，通过将复杂问题分解为更小的、相互关联的子问题，然后逐个解决这些子问题，最终组合成原问题的解决方案。动态规划的关键在于避免重复计算，通过存储子问题的解来提高效率。 在实施动态规划时，通常遵循以下四个基本步骤： 1. **分析最优解的结构**：首先需要理解一个问题的最优解应具备什么样的特征。这可能涉及到最短路径、最大收益或最小成本等问题的结构。 2. **递归定义最优解**：定义一个递归公式，该公式描述了问题的子问题如何相互关联，并且如何通过这些子问题的解来构建原问题的最优解。 3. **自底向上的计算**：从最小规模的子问题开始，逐步计算更大的子问题，直到解决原问题。这个过程通常通过填充一个表格（也称为状态转移矩阵）来完成，其中每个单元格存储对应子问题的最优值。 4. **构造最优解**：根据计算最优值过程中记录的信息，反向追溯以构建出原问题的最优解。 以南京理工大学的费氏数列为例，它展示了动态规划的应用。费氏数列是一个典型的递归序列，其中每个数是前两个数的和。直接的递归实现虽然简单，但效率极低，因为存在大量的重复计算。例如，计算`Fib(n)`时会多次计算`Fib(n-1)`和`Fib(n-2)`。 为了提高效率，我们可以使用动态规划的方法，预先存储中间计算结果，避免重复计算。通过初始化`f1`和`f2`为1，然后用循环迭代计算出整个序列，每次迭代将`f1`和`f2`的和赋值给新的结果，然后更新`f1`和`f2`的值。这样，每个数只计算一次，时间复杂度从原来的指数级降低到线性级，大大提高了效率。 动态规划与分治法的主要区别在于，分治法通常将问题分解为独立的部分，而动态规划则关注子问题之间的重叠和依赖关系。在分治法中，子问题的解是相互独立的，而在动态规划中，子问题的解是相互关联的，通过存储和复用子问题的解来减少计算量。 动态规划适用于许多领域，如最短路径问题（如Dijkstra算法）、背包问题、矩阵链乘法等。它不仅在理论上具有重要的地位，而且在实际应用中也有广泛的价值，因为它能够有效地处理那些具有重叠子问题和最优子结构特征的复杂问题。