清华大学田永鸿程序设计实习：链表与二叉树的动态规划解析

“程序设计实习（田永鸿)清华大学”是一个针对ACM竞赛和C语言编程的实习课程，由清华大学的田永鸿教授主讲。课程内容涵盖了基础的算法和数据结构，如链表和二叉树，同时也涉及动态规划和递归等程序设计方法。 在动态规划（Dynamic Programming, DP）部分，讲解了记忆化搜索，这是动态规划的核心思想。首先，需要找到子问题，确定问题的状态，然后建立状态转移方程。动态规划与递归的主要区别在于处理重复计算的方式：如果不存在重复计算，或者重复计算对效率影响不大，可以使用递归；但如果重复计算很多，为了提高效率，就应采用动态规划。 课程中提到了一个问题，即在数字三角形中寻找从顶部到底部路径的最小存储开销。这个问题可以通过动态规划来解决，通过存储每一层的最优选择来避免重复计算，从而降低内存使用。 另一个例子是POJ1661HelpJimmy问题，这是一个关于一只老鼠从板子上掉下来的故事。书中给出了递归的解决方案，而动态规划（动归）解法则更适合这个问题，因为它可以有效地处理重复的子问题。动态规划解法的主要思想是自底向上地构建解决方案，通过存储之前计算过的状态来避免重复计算，这通常比递归更高效。 在代码示例中，可以看到一个用C++实现的动态规划解决方案，用于处理HelpJimmy问题。代码定义了一个`Board`结构体来存储每块板子的高度、左边和右边的边界。使用`qsort`进行排序，以便从高到低处理板子。同时，定义了二维数组`f`来存储到达每个位置的最小距离。`min`函数用于比较两个值并返回较小的一个，`LEFTRIGHT`、`LEFT`和`RIGHT`是布尔变量，可能用于判断老鼠是否可以向左、向右或两边移动。 这个课程对于初学者来说是很好的学习资源，它不仅介绍了基本的编程概念，还深入讲解了如何解决复杂问题的策略和技巧，特别是动态规划的应用，这对于参加ACM竞赛或提升程序设计能力非常有帮助。