动态规划解题艺术：公主城堡与数字三角形

动态规划是一种在计算机科学中广泛应用的算法策略，特别是在ACM程序设计竞赛中，它被广泛用于解决优化问题。在这份浙江大学ACM动态规划讲义中，作者首先强调了动态规划在信息学竞赛中的重要性，它因其能够处理复杂的多阶段决策问题而受到青睐。 讲义从动态规划的基本概念开始，将其与搜索算法进行对比。例如，通过数字三角形问题（如Fibonacci数列的变种）来解释如何通过状态转移方程来解决问题。在这个场景中，动态规划的实质是通过预先计算并存储中间结果（记忆化搜索），避免重复计算，从而降低时间复杂度。状态转移方程通常表示为一个递推公式，如f(i,j) = a[i,j] + min{f(i-1,j), f(i-1,j+1)}，展示了问题由子问题组合而成的结构。 讲义还介绍了两种常见的动态规划方法：直接使用循环表示法，适用于较简单的状态和转移；对于复杂情况，可以采用记忆化搜索（也称为自底向上的动态规划），通过创建一个数组（如opt数组）来存储已经计算过的最优解，避免重复计算。记忆化搜索使得问题的求解过程更加直观，编程难度降低，而且运行时间只比非记忆化版本增加一个常数，这对于比赛中的效率至关重要。 此外，动态规划并不是孤立的技术，它往往与其他算法技巧结合使用，如贪心算法、回溯法等，以应对不同类型的优化问题。理解动态规划的核心思想——将大问题分解为小问题，再利用已知最优解来求解当前问题，是提升算法竞赛解题能力的关键。 总结来说，这份讲义深入浅出地讲解了动态规划的概念、基本应用以及在解决数字三角形问题中的具体操作，强调了记忆化搜索在优化时间复杂度方面的优势，为ACM竞赛选手提供了解决复杂优化问题的有效工具。