视频字幕
动态规划是一种重要的算法设计技术，专门用于解决具有重叠子问题和最优子结构性质的优化问题。让我们通过递归树来理解为什么需要动态规划。在传统的递归方法中，我们会遇到大量的重复计算。比如在这个递归树中，f(3)被计算了两次，f(2)被计算了三次，f(1)被计算了五次。这些重复的计算导致了指数级的时间复杂度。动态规划通过存储这些子问题的解，避免重复计算，从而大大提高算法效率。
让我们通过斐波那契数列来具体理解动态规划的优势。斐波那契数列的递归公式是F(n)等于F(n-1)加F(n-2)。如果用传统递归方法，时间复杂度是O(2的n次方)，这是指数级增长，效率很低。而动态规划方法使用dp数组存储中间结果，dp[n]等于dp[n-1]加dp[n-2]，时间复杂度只有O(n)，是线性增长。从这个对比表可以看出，当n等于4时，递归方法需要9次计算，而动态规划只需要5次。动态规划采用自底向上的计算方式，先计算小规模问题，再逐步构建大规模问题的解。
动态规划有一套标准的解题步骤，掌握这个框架可以帮助我们系统地解决各种动态规划问题。第一步是定义状态，我们需要明确dp数组中每个元素代表什么含义，这是解题的基础。第二步是找出状态转移方程，这是动态规划的核心，需要找出当前状态与之前状态之间的递推关系。第三步是确定初始条件，也就是边界条件和初始值，这些是递推的起点。第四步是确定计算顺序，要保证在计算当前状态时，所依赖的状态已经被计算出来。这四个步骤环环相扣，形成了完整的动态规划解题思路。
现在我们通过0-1背包问题来深入理解动态规划的应用。背包问题是这样的：给定n个物品，每个物品有重量和价值，背包有容量限制，求能装入背包的物品的最大价值。我们定义状态dp[i][w]表示前i个物品在容量为w时的最大价值。状态转移方程是：对于每个物品，我们有两个选择，要么不选择这个物品，价值就是dp[i-1][w]；要么选择这个物品，价值就是dp[i-1][w-重量]加上当前物品的价值。我们取两者的最大值。通过这个二维表格，我们可以看到动态规划如何逐步填充每个状态，最终得到最优解。
最长公共子序列问题是动态规划在字符串处理中的经典应用。给定两个字符串，我们要找出它们最长的公共子序列。我们定义dp[i][j]表示第一个字符串前i个字符与第二个字符串前j个字符的最长公共子序列长度。状态转移方程分两种情况：如果当前字符相同，则dp[i][j]等于dp[i-1][j-1]加1；如果不同，则取dp[i-1][j]和dp[i][j-1]的最大值。通过这个二维网格，我们可以看到算法如何逐步填充每个位置，绿色箭头表示字符匹配的情况，蓝色箭头表示字符不匹配时的选择。最终我们得到字符串ABCD和ACBD的最长公共子序列是ACD，长度为3。