动态规划入门：数字三角形求最大和

动态规划基础讲解 - 数字三角形求最大和问题 动态规划是一种算法设计技术，主要用于求解具有重叠子问题和最优子结构的问题，通过将大问题分解为相互关联的小问题，然后将这些小问题的解组合起来得到原问题的解。在这个例子中，问题涉及到寻找一个数字三角形中从顶点到底部的最佳路径，使得路径上所有数字之和最大。 问题描述中提到的数字三角形是一个经典的动态规划问题，如第9课中的综合实践考核题目。给定一个N行的三角形，每行的数字从1到N递增，且每个数在0到100范围内。目标是找到从左上角到右下角的路径，使得路径上数字之和最大。由于路径限制，每次只能向右或向下移动到相邻的数字。 解题思路的核心在于定义状态变量和递推关系。设D[r][j]表示第r行第j个数字，MaxSum(r, j)代表从第r行的第j个数字到底部的最佳路径的数字之和。根据题目条件，我们可以通过比较MaxSum(r+1, j)和MaxSum(r+1, j+1)来决定当前数字应与左邻或右邻的数字相连，从而更新MaxSum(r, j)的值。 参考程序I中，使用了递归方法来实现这个过程。函数MaxSum(r, j)首先检查是否到达最后一行，如果是，则返回D[r][j]；否则，分别计算沿着右邻和下邻路径的可能最大和，选择其中较大者加上当前数字作为新的MaxSum。主函数通过读取输入的三角形数据，并调用MaxSum(1, 1)来计算最终的最大和。 需要注意的是，虽然递归是一种直观的解决方案，但在这里并不推荐直接使用递归，因为递归会导致大量的重复计算。动态规划的关键在于使用一个二维数组来存储中间结果（如MaxSum[r][j]），这样在后续计算中可以直接利用已知最优解，避免重复工作，大大提高了效率。 总结，动态规划在解决此类问题时，需要明确状态转移方程、初始化状态、以及如何通过已知最优解来更新状态。在实际编程中，将递推逻辑转换为迭代形式，如使用循环遍历，可以更好地应用到C++、C等编程语言中，并优化ACM（算法竞赛）题目中的性能。