ACM动态规划题解：最大数字和路径与递归函数

"这篇资料是关于ACM竞赛中动态规划(DP)的总结，包含了两道具体的动态规划题目，旨在帮助学习者理解和掌握这一重要算法。资料提供了详细的解题思路和部分源代码，适合用于学习和实践。" 动态规划是一种在计算机科学中广泛使用的算法设计方法，特别适用于解决具有重叠子问题和最优子结构的问题。在这个ACM动态规划总结中，作者通过两道北京大学PKU 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]; } } ``` 第二题是"Pkuacm1579 Function RunFun"，这是一个涉及三参数递归函数的题目。函数`w(a, b, c)`根据给定条件有不同的返回值。直接递归求解会导致超时（TLE），因此采用动态规划的方法，预先计算并存储所有可能的`w(a, b, c)`值，避免重复计算。问题的解决策略是自底向上地填充一个三维数组，从`w(0, 0, 0)`开始，直到`w(20, 20, 20)`。这样，复杂度降低到`O(n^3)`，可以接受。这个例子很好地展示了如何用动态规划处理具有大量重叠子问题的递归函数。 这两道题目的解法都体现了动态规划的核心思想：通过储存子问题的解来避免重复计算，从而提高效率。动态规划通常分为自底向上和自顶向下两种方式，这两题分别展示了这两种方法的应用。学习动态规划不仅可以提升在ACM竞赛中的竞争力，也有助于解决实际编程中的优化问题。在实际应用中，理解如何识别问题的最优子结构和重叠子问题，以及如何构建状态转移方程，是掌握动态规划的关键。