视频字幕
动态规划是计算机科学中一种重要的算法设计技术。它通过将复杂问题分解为更简单的子问题来求解。动态规划的核心思想是避免重复计算，通过存储子问题的解来提高算法效率。它适用于具有最优子结构和重叠子问题特性的问题。
动态规划有两个关键特性。第一是最优子结构，即原问题的最优解包含子问题的最优解。第二是重叠子问题，在递归求解过程中会多次遇到相同的子问题。以斐波那契数列为例，计算F(n)需要计算F(n-1)和F(n-2)，而F(n-1)又需要计算F(n-2)和F(n-3)，这样F(n-2)就被重复计算了。
动态规划的解题有四个基本步骤。首先定义状态，确定用什么变量来表示子问题。然后建立状态转移方程，找到不同状态之间的关系。接着确定边界条件，即最简单情况的解。最后确定计算顺序，通常是从小到大依次计算所有状态，确保计算某个状态时其依赖的子问题都已解决。
让我们用斐波那契数列来演示动态规划。斐波那契数列定义为F(0)等于0，F(1)等于1，对于n大于1，F(n)等于F(n-1)加F(n-2)。我们定义状态F(i)表示第i个斐波那契数，状态转移方程就是F(i)等于F(i-1)加F(i-2)，边界条件是F(0)等于0和F(1)等于1。我们按从小到大的顺序计算每个值。
动态规划在计算机科学和数学中有着广泛的应用。它可以解决最短路径问题，如寻找图中两点间的最短距离。在背包问题中，动态规划帮助我们在有限容量下选择最优物品组合。它还用于解决最长公共子序列、编辑距离等字符串处理问题，以及股票买卖、硬币找零等优化问题。动态规划是算法设计中的重要工具。