ACM动态规划题目总结：经典实例解析

"ACM动态规划总结，包括两个具体的动态规划题目——Pkuacm1163 The Triangle 和 Pkuacm1579 Function Run Fun 的解题思路与代码解析。" 在ACM（国际大学生程序设计竞赛）中，动态规划是一种常用于解决复杂问题的算法策略。它通过将问题分解成更小的子问题，然后逐个解决这些子问题，最终组合成原问题的解决方案。这里我们聚焦于两个典型的动态规划题目。 首先，Pkuacm1163 "The Triangle" 是一个寻找最大路径和的问题。给定一个数字构成的三角形，目标是从任意一个叶子节点出发，找到一条到达根节点的路径，使得路径上所有数字之和最大。解决这个问题的关键在于自底向上的动态规划。我们初始化一个二维数组 `number`，从下往上填充，每个元素表示其下方两个子节点到当前节点的最大路径和。核心代码如下： ```java for(int i = num - 2; i >= 0; i--){ for(int j = 0; j <= i; j++){ number[i][j] = Math.max(number[i + 1][j], number[i + 1][j + 1]) + number[i][j]; } } ``` 这段代码中，`number[i][j]` 更新为其左子节点和右子节点中的最大值加上自身，这样从叶子节点到根节点的最优路径就被记录下来了。 其次，Pkuacm1579 "Function Run Fun" 需要处理一个三参数的递归函数 `w(a, b, c)`。函数的定义涉及到多种情况，如果直接递归计算会导致超时。因此，我们可以使用动态规划，预先计算并存储所有可能的 `(a, b, c)` 组合的结果。从 `w(0, 0, 0)` 开始，逐步递推到 `w(20, 20, 20)`。这个问题的难点在于子问题数量众多，使用递推的方法可以有效地避免重复计算，降低时间复杂度至 O(n^3)。这种策略被称为“自底向上的递推”，在刘汝佳的《算法艺术和信息学竞赛》中有详细介绍。 这两个题目都展示了动态规划在解决复杂计算问题时的强大能力。它们不仅要求参赛者理解递归，还要求他们能够识别问题的结构并构建有效的状态转移方程。理解和掌握这类问题的解法对于提升ACM竞赛水平至关重要。