北京大学暑期课《ACM/ICPC竞赛训练》- 动态规划详解

"北京大学暑期课《ACM/ICPC竞赛训练》主要讲解了动态规划这一算法，通过实例分析了如何解决数字三角形问题，并探讨了动态规划中的递归计算及其可能导致的时间复杂性问题。" 在计算机科学和算法竞赛中，动态规划（Dynamic Programming, DP）是一种强大的解决问题的方法，尤其适用于解决最优化问题。北京大学暑期课《ACM/ICPC竞赛训练》由郭炜教授主讲，课程深入浅出地介绍了动态规划的概念和应用。 动态规划的核心思想是将一个复杂的问题分解成多个相互关联的子问题，然后通过解决这些子问题来找到原问题的最优解。这种方法通常涉及到多阶段决策过程，且后一阶段的决策依赖于前一阶段的决策结果。 课程中的例题“数字三角形”（POJ1163）是一个经典的动态规划问题。问题要求从一个数字三角形的顶部到底部找到一条路径，使得路径上数字之和最大。每一步只能向左下或右下移动。给定三角形的行数（N）大于1且小于等于100，数字范围在0到99之间。 为了解决这个问题，郭炜教授提出了以下的解题思路： 1. 使用二维数组`D[r][j]`存储数字三角形的每个元素。 2. 定义`MaxSum(r,j)`表示从`D[r][j]`到达三角形底部的最优路径的数字之和。 3. 当到达最后一行（即`r==N`）时，`MaxSum(r,j)`就等于当前数字`D[r][j]`。 4. 对于非最后一行，`MaxSum(r,j)`是其下一行的两个子问题`MaxSum(r+1,j)`和`MaxSum(r+1,j+1)`的最大值加上当前数字`D[r][j]`。 给出的C++代码实现了一个递归解决方案，但这个递归版本会存在大量的重复计算，导致效率低下，可能会在大输入规模下引发超时。例如，当三角形的大小增加时，递归树的分支会急剧增长，从而导致时间复杂度呈指数级增长。 为了解决这个问题，通常会使用动态规划的迭代方法，也称为自底向上法。在这个过程中，我们从底层的`MaxSum`值开始逐步向上计算，避免了重复计算，大大提高了算法效率。迭代版本的`MaxSum`数组可以直接存储所有中间结果，使得计算过程更高效。 动态规划是编程竞赛和实际问题解决中的重要工具，它要求对问题进行结构化分析，将问题分解为子问题并有效地存储和利用子问题的解。北京大学的这门课程通过实例教学，帮助学生掌握动态规划的核心思想和技巧，从而提高他们在ACM/ICPC等算法竞赛中的竞争力。