清华大学DP讲义：动态规划基础与优化

"DP总结.pdf 是清华大学的一份关于动态规划(DP)的讲义，涵盖了状态类型、转移方式和DP优化等内容，适用于算法学习和理解。" 动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题的算法，通常用于处理具有重叠子问题和最优子结构的复杂问题。这份讲义主要分为三个部分：状态类型、转移方式和DP优化。 1. **状态类型**： - **序列DP**：这是最基础的状态类型，状态通常定义为与序列中的位置有关，如第i个位置的状态。分为两种编号方式： - 状态[i]表示前i个元素决策组成的当前状态。 - 状态[i]表示使用了第i个元素，并结合1到i-1的元素决策组成的当前状态。 - **区间DP**：状态涉及两个或多个连续的序列元素，如区间[i, j]的状态。 - **坐标DP**：状态与特定坐标或坐标范围相关联。 - **数轴DP**：涉及到数轴上的点或区间的状态。 - **树型DP**：状态与树的节点或子树有关。 - **数位DP**：考虑数字的每一位进行状态定义。 - **状压DP**：使用位运算来表示状态，减少状态数量。 - **记忆化搜索**：虽然不是严格意义上的DP，但通过存储中间结果来避免重复计算，提高效率。 2. **转移方式**： - 动态规划的核心在于状态转移方程，它描述了如何从一个或多个相邻的状态转移到下一个状态。在序列DP中，常见的转移方式是通过前i-1个元素来更新状态[i]，或者使用第i个元素和其他元素共同决定新的状态。 3. **DP优化**： - **空间优化**：如采用滚动数组或部分状态压缩来减少空间需求，例如从O(n^2)优化到O(n)。 - **单调队列/栈**：在区间DP中，利用单调性质可以使用单调队列或栈进行优化，如LIS（最长递增子序列）问题。 - **二分查找**：在某些问题中，可以通过二分查找加速状态查找过程，如LIS问题。 - **记忆化搜索**：避免重复计算，提高时间效率。 - **状态压缩**：对于多维状态，有时可以通过位运算将多维状态压缩为一维，如状压DP。 讲义还提到了一些具体的问题，如LIS和LCS（最长公共子序列）问题，它们都是经典的动态规划问题。LIS问题通过单调数组和二分查找可以达到O(n log n)的时间复杂度；而LCS问题，状态定义为两个字符串的对应位置，可以扩展到多个字符串的LCS问题。 这份讲义提供了对动态规划全面且深入的理解，包括其基本概念、不同类型的状态表示以及常见优化策略，对于学习和掌握动态规划算法非常有帮助。