动态规划入门：记忆化搜索解数字三角形问题

"本文主要介绍了记忆化搜索算法在动态规划中的应用，特别是在解决数字三角形问题上的实例。动态规划是一种重要的算法，它在信息学竞赛中占有重要地位，需要较高的数学理解和问题解决能力。文章首先指出动态规划并不遵循固定模式，初学者需要通过大量实践来掌握。接着，文章回顾了动态规划在IOI、NOI和NOIP等竞赛中的经典题目，如数字三角形、石子合并和导弹拦截问题。然后，文章以数字三角形问题为例，详细阐述了如何使用记忆化搜索算法寻找数字三角形中数字之和的最大路径，并给出了算法实现。最后，文章提供了基于深度优先搜索的算法实现，通过递归地探索左下和右下两个方向来更新答案。" 在动态规划算法初步中，记忆化搜索是一种优化手段，用于避免重复计算。在这个例子中，我们处理的是一个数字三角形问题，目标是找到从顶层到底层的路径，使得路径上数字之和最大。记忆化搜索的关键在于利用一个二维数组`f[i][j]`来存储从`(i, j)`到最后一行的和的最大值。数组的初始值设为-1，表示尚未计算过。当到达最后一行时，`f[i][j]`等于当前位置的数字`a[i][j]`。 算法的核心是`dfs(i, j)`函数，它递归地计算从`(i, j)`出发的最优路径。在进入函数之前，首先检查`f[i][j]`是否已经计算过，如果大于等于0，则说明该状态已解决，直接返回。否则，分别对`(i+1, j)`和`(i+1, j+1)`进行递归调用，之后将这两个结果中的较大值加上`a[i][j]`作为`f[i][j]`的值，这确保了我们总是选择当前路径下的最优解。 代码实现中，`dfs(i, j, sum)`函数接收当前行`i`、列`j`和当前路径的和`sum`。当到达最后一行时，比较`sum`与当前最优答案`ans`，并更新`ans`。然后分别对左下和右下两个方向进行递归调用，每次调用都将当前行的数字加入到`sum`中。 这个过程是自底向上的，从数字三角形的底层开始，逐层向上计算最优路径，直到顶层。通过记忆化搜索，我们只需要计算每个状态一次，避免了回溯和重复计算，提高了算法的效率。这样的方法对于解决具有重叠子问题的动态规划问题非常有效。 总结来说，动态规划是一种解决问题的策略，它通过将复杂问题分解成一系列子问题并存储子问题的解来逐步构建出原问题的解。记忆化搜索是动态规划的一种优化，通过记录子问题的解来避免重复计算，提高了算法执行效率。在处理数字三角形这类问题时，记忆化搜索算法能有效地找出最优路径。