南京理工大学动态规划解析：费氏数列与优化方法

"南京理工大学的课程资料，涉及动态规划算法的实例讲解，通过费氏数列展示了动态规划解决效率问题的方法。" 在动态规划（Dynamic Programming，简称DP）这一领域，我们通常会遇到一个问题，即如何有效地处理那些可以通过解决较小子问题来构建整体解的问题。动态规划是一种优化技术，它通过将复杂问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算，从而提高效率。 在给出的实例中，描述了一个表格`C[i,j]`，这可能是表示某个决策过程或资源分配问题的成本或最优解。例如，`C[1,5]=348`可能意味着从状态1到状态5的最小成本路径是348。这里的每个`Mx`标记可能代表一种特定的决策或动作，比如 `(M1 M2)` 指的是执行操作M1后再执行操作M2。 费氏数列（Fibonacci sequence）是动态规划的经典示例。费氏数列的定义是：`F(0)=0`, `F(1)=1`, `F(n)=F(n-1)+F(n-2)`对于`n>1`。在初始的递归实现中，虽然代码简单，但效率极低，因为存在大量的重复计算。例如，计算`F(n)`时会重复计算`F(n-1)`和`F(n-2)`，这些值在之前的递归调用中已经被计算过。 为了解决这个问题，我们可以采用动态规划的方法，即保存之前计算过的子问题结果。在迭代过程中，我们首先初始化`f1=1`, `f2=1`，然后从`i=3`到`n`，每次计算`f1`和`f2`的和赋值给`result`，然后更新`f1`和`f2`的值。这样，我们避免了重复计算，时间复杂度从原来的指数级降低到了线性级，大大提高了效率。 动态规划与分治法的主要区别在于，分治法通常将问题分解为独立的子问题，而动态规划则侧重于子问题的重叠性质，即子问题的解可以被用来构建更大的问题的解。在动态规划中，子问题的解会被存储并重复使用，而在分治法中，子问题的解通常是独立的，不会被再次利用。 动态规划是一种强大的工具，尤其适用于解决那些具有重叠子问题和最优子结构的问题，如最短路径、背包问题、矩阵链乘法等。通过理解和应用动态规划，我们可以设计出更高效、更优的算法，有效减少计算量，提高问题求解的效率。