动态规划解析：清华大学计算机课件

"这是一份来自清华大学计算机课程的讲义，专注于动态规划这一主题，由李晓潇教授讲解。课程内容包括多个例题和习题，旨在帮助学习者深入理解和应用动态规划解决实际问题。" 动态规划是一种重要的算法设计方法，广泛应用于计算机科学和数学中，特别是对于解决优化问题。在清华大学的这门课程中，动态规划被详细地讲解，通过具体的例子和习题来阐述其核心概念。 首先，动态规划通常用于解决具有重叠子问题和最优子结构的问题。以题目中提到的“数字三角形”为例，贪心算法无法找到最优解，因为它只关注当前选择的最大值，而忽略了后续可能的影响。而搜索算法虽然能找出最优路径，但效率低下，因为它会重复计算相同的子问题。 动态规划的优势在于它可以避免这种重复计算，通过存储子问题的解来提升效率。在数字三角形问题中，状态可以用 `f[i][j]` 表示，其中 `i` 和 `j` 分别代表行数和列数，表示以第 `i` 行第 `j` 个数字为顶点的子三角形的最优路径的数值和。动态规划的转移方程为 `f[i][j]=max{f[i+1][j],f[i+1][j+1]}+a[i][j]`，表示当前节点的最优解是其左子节点或右子节点的最优解与当前节点值的最大值。边界条件是最后一行的 `f[n][i]=a[n][i]`，即最底层的节点值即为最优解。 动态规划的四个关键步骤包括： 1. 描述最优解的结构：定义问题的状态空间。 2. 状态表示：确定每个状态的意义和表示方式。 3. 递归定义最优解的值：建立状态之间的关系，形成状态转移方程。 4. 按自底向上的方式计算最优解的值：通过迭代计算，从基础情况开始逐步构建到复杂情况的最优解。 在动态规划中，序列、区间、网格、树形结构和状态压缩都是常见的状态表示方式。转移方程的设计往往涉及预处理、数据结构的选择以及利用单调性来优化算法。动态规划还可以根据问题的特点进行分类，如序列问题、区间问题等。 以最长公共子序列问题为例，给定两个序列X和Y，目标是找到它们的最长公共子序列。动态规划可以通过构建二维数组来存储X和Y的子序列信息，然后按照状态转移方程逐步计算出最长公共子序列。在这个问题中，如果两个字符匹配，最长公共子序列的长度就是前一个子问题的长度加一；如果不匹配，则取两者长度中的较大值。 动态规划与搜索、递推有着密切的关系，它能够更高效地解决具有重复子问题的优化问题，通过记忆化搜索或自底向上的迭代方法实现。拓扑图在某些动态规划问题中可以用来直观展示状态之间的依赖关系。 清华大学的这门课程深入探讨了动态规划的基本原理和应用，通过实例和习题提供了丰富的学习材料，有助于学习者掌握这一核心算法。