ACM解题：动态规划与数字三角形

"ACM 动态规划之数字三角形，主要介绍了如何解决数字三角形问题，包括递归、动态规划（递推）和记忆化搜索三种方法。" 在计算机科学和算法竞赛，如ACM（国际大学生程序设计竞赛）中，动态规划是一种强大的工具，用于解决复杂的问题，数字三角形问题就是其中之一。这个问题涉及到在一个由数字构成的三角形中，从顶部到底部找到一条路径，使得路径经过的所有数字之和最大。 1. **递归方法**：最直观的方法是通过递归来解决。代码中的`d(i,j)`函数代表到达三角形中位置`(i,j)`的最大路径和。递归公式可以表示为：`d(i,j) = a[i][j] + max(d(i+1,j), d(i+1,j+1))`，其中`a[i][j]`是三角形中当前位置的数值。这种方法虽然直观，但效率较低，因为存在大量的重复计算。 2. **动态规划（递推）方法**：为了优化递归解法，我们可以使用动态规划（DP）来避免重复计算。在二维数组`d[][]`中存储每个位置的最大路径和，从底部向上计算。对于位置`(i,j)`，其动态规划状态转移方程为：`d[i][j] = max(d[i+1][j], d[i+1][j+1]) + a[i][j]`。这种方法显著提高了效率，因为它只计算每个状态一次。 3. **记忆化搜索**：记忆化搜索是另一种优化递归的方法，它使用一个额外的数组`d[][]`来存储已计算过的子问题结果，避免了重复计算。在代码中，如果`d[i][j]`的值已经计算过，就直接返回，否则进行计算并保存结果。这种方法与动态规划类似，但更适用于非最优顺序的求解过程。 以上三种方法都是为了解决相同的问题，即在数字三角形中找到最大路径和。递归方法简单但效率低，动态规划和记忆化搜索则通过存储中间结果提高效率。在实际应用中，动态规划方法是最常见且高效的解决方案。在ACM竞赛中，选手需要根据问题的特点和时间限制选择合适的方法。