动态规划解析：从多米诺骨牌到记忆化搜索

"多米诺骨牌-浙江大学 ACM程序设计竞赛-动态规划讲义" 这篇讲义主要探讨了动态规划在解决ACM程序设计竞赛中的应用，特别是通过一个关于多米诺骨牌的问题来阐述动态规划的基本思想和常用方法。动态规划是一种在计算机科学中广泛使用的算法，它通过构建有序的子问题解决方案来解决复杂问题，通常用于优化问题，特别是在有重叠子问题和最优子结构的条件下。 讲义首先介绍了动态规划的概念，并将其与搜索算法进行了对比。以数字三角形问题为例，解释了如何使用动态规划找到路径权值之和最小或最大的路径。在这个问题中，状态转移方程f(i,j)=a[i,j]+min{f(i-1,j), f(i-1,j+1)} 揭示了如何从上一层的状态计算当前层的状态。这表明动态规划的核心在于状态的定义、状态转移方程的建立以及状态之间的递推关系。 接着，讲义提到了记忆化搜索作为动态规划的一个变体。在搜索算法中，通过使用记忆化技术存储中间结果，可以避免重复计算，显著提高效率。例如，在数字三角形问题的递归过程中，可以维护一个二维数组opt[i][j]来存储每个f(i,j)的最优值，这样在后续的计算中可以直接读取，而不是重新计算。 此外，讲义还讨论了动态规划的一些特殊形式，包括但不限于： 1. 背包问题：这类问题通常涉及在容量限制下选择物品以达到最大价值或最小重量，如完全背包、0/1背包等。 2. 最短路径问题：如Dijkstra算法和Floyd-Warshall算法，它们寻找图中两个节点间的最短路径。 3. 最长公共子序列（LCS）问题：在两个序列中寻找最长的非空子序列，该子序列在两个原始序列中都存在，但不一定连续。 动态规划的应用广泛，不仅限于ACM竞赛，还涵盖了组合优化、图论、字符串处理等多个领域。它要求程序员具备清晰的逻辑思维，能够识别和分解问题，建立状态和状态转移方程，以及合理利用空间存储中间结果。 动态规划是一种强大的工具，通过理解和掌握动态规划，不仅可以解决许多复杂问题，还能培养解决问题的系统性和深度。在ACM竞赛中，熟练运用动态规划往往能帮助参赛者在有限的时间内找到高效解法，从而取得好成绩。