视频字幕
动态规划是计算机科学中一种重要的算法设计技术。它的核心思想是将一个复杂的问题分解成若干个相互重叠的子问题，然后通过存储这些子问题的解来避免重复计算，从而显著提高算法的效率。这种方法特别适用于具有最优子结构和重叠子问题特性的问题。
动态规划有两个关键特性。第一个是最优子结构，即问题的最优解可以通过其子问题的最优解来构建。第二个是重叠子问题，在递归求解过程中会多次遇到相同的子问题。以斐波那契数列为例，计算F(5)时会重复计算F(3)和F(2)等子问题，这就是重叠子问题的体现。
让我们通过斐波那契数列来理解动态规划。斐波那契数列的定义是F(0)等于0，F(1)等于1，F(n)等于F(n-1)加F(n-2)。传统的递归方法时间复杂度是指数级的，而动态规划通过建立一个表格，从小到大依次计算并存储每个值，将时间复杂度降低到线性级别。
动态规划有两种主要的实现方法。第一种是自顶向下的记忆化递归，从目标问题开始，递归地求解子问题，并用备忘录存储已计算的结果。第二种是自底向上的表格填充方法，从最小的子问题开始，逐步构建解决方案，填充动态规划表格。两种方法的时间复杂度相同，但在空间使用上略有不同。
动态规划在计算机科学和实际应用中有着广泛的用途。它可以解决背包问题、最短路径问题、最长公共子序列、编辑距离、股票买卖、硬币找零等众多经典问题。通过将复杂问题分解为子问题并避免重复计算，动态规划成为了解决优化问题的强大工具。掌握动态规划的思想和方法，能够帮助我们高效地解决许多实际中遇到的复杂问题。