动态规划算法实例：数字三角形中路径和最大值

"动态规划算法初步讲解" 每个点的计算次数 n=10 的问题涉及的是一个经典的动态规划问题，即数字三角形中的路径和最大化问题。在信息学竞赛中，特别是国际奥林匹克信息学竞赛（IOI）中，这类问题被广泛应用，如1994年的数字三角形挑战。动态规划是一种解决优化问题的算法方法，它通过将大问题分解成更小、相互重叠的子问题，并存储子问题的解来避免重复计算。 动态规划的核心思想是将问题分解成子问题，并用一个表格（通常称为状态数组或动态规划表）来存储这些子问题的最优解。在这个例子中，状态数组a[i][j]存储了从左上角走到第i行第j列时路径上的数字总和，其中i和j分别表示行和列的位置。为了找到最大和路径，算法采用深度优先搜索（DFS）的思想，首先尝试向下或向右走，然后递归地调用自身处理下一行或下一行的相邻位置。 对于数字三角形问题，DFS函数`dfs(i, j, sum)`负责计算从起点(1,1)到当前位置(i, j)的路径和，并与当前已知的最大和进行比较。如果当前路径和大于已知的最大和，就更新最大和。当到达最后一行（n行）时，返回最大和作为结果。 代码实现的关键部分包括初始化动态规划表、递归调用dfs函数以及在每个递归调用中更新最大和。例如，`dfs(i+1,j,sum+a[i+1,j])`表示考虑向右下走，而`dfs(i+1,j+1,sum+a[i+1,j+1])`表示向右下走。这样，每次调用都会检查是否找到了新的最大和路径。 数字三角形问题展示了动态规划算法如何通过存储中间结果来解决具有重叠子问题和最优子结构特征的问题。理解并熟练运用动态规划不仅可以提升在信息学竞赛中的解题能力，而且对于解决现实生活中的优化问题也有重要作用。学习过程中，多做题并深入理解问题背后的数学原理至关重要，单纯会解题并不意味着完全掌握了动态规划这一高级算法技巧。