动态规划解题策略：数塔与最长有序子序列

威威猫系列故事——打地鼠是一堂关于ACM程序设计的课程，由杭州电子科技大学刘春英教授讲解，课程内容涵盖动态规划这一核心概念。动态规划是一种在优化问题中常用的算法设计技巧，通过将原问题分解为相互重叠的子问题，并存储已解决的子问题结果，避免重复计算，从而提高求解效率。 首先，课程介绍了经典问题——数塔问题，它涉及从塔顶到达底部，每一步可以选择向左或向右，目标是找到价值最大的路径。暴力枚举方法在处理大量层级时效率极低，因为它会计算无数不必要的路径，比如在31层塔中可能需要检查的路径数量将超过10亿。为了解决这个问题，教授强调了动态规划的自顶向下分析和自底向上计算策略，即先确定所有可能的最优路径，然后逐层递归地决定当前步骤的最佳选择。 第二个经典问题是“最长有序子序列”问题，该问题要求找到一个数组中最长的保持元素顺序的子序列。通过构建一个辅助数组来记录每个位置的最大前缀和，可以有效地找到答案。课程中给出了一个具体例子，展示了如何使用动态规划求解输入数组1到9的最长有序子序列问题。 在“思考：免费馅饼”部分，教授可能引导学生思考如何将动态规划应用于类似的问题情境，鼓励他们提出自己的见解和解决方案。此外，“再思考”可能是对先前讨论的深入反思或者引入新的相关问题进行讨论，激发学生的思考和实践能力。 这堂课通过实际问题展示了动态规划在解决复杂问题中的威力，强调了算法设计中的策略性思维和问题分解的重要性，帮助学生提高在竞赛编程中的问题解决能力。同时，也培养了他们运用递推和分治思想来优化求解过程的技能。