刘汝佳动态规划经典问题详解：最长子序列与最优排序

动态规划经典问题，由刘汝佳编写，是一份深入浅出的教程，主要讲解了几个常见的动态规划问题及其解决方案。本教程分为八个部分，涵盖了动态规划在实际问题中的广泛应用。 1. **最长公共子序列 (LCS)**: 这是基础的动态规划问题，通过递推公式 `c[i,j] = |LCS(x[1..i],y[1..j])|` 计算两个序列的最长公共子序列长度。关键点在于问题的最优子结构和重叠子问题特性，利用记忆化搜索进行优化。空间复杂度可以通过滚动数组降低到O(min{m,n})，甚至进一步优化为一行，只保留相邻两行的值。 2. **最优排序二叉树**: 问题目标是构建一个排序二叉树，使得期望的比较次数最少。通过递归性质，证明子树也是最优的，解决时需要考虑将频率最高的关键码作为根节点，构建左右子树。 3. **最长上升子序列 (LIS)**: 时间复杂度为O(nlogn)，通过观察序列的单调性，找到最长的严格递增子序列。 4. **最优三角剖分**: 涉及二维空间内分割区域的问题，其解法通常需要O(n^3)的时间复杂度，通过动态规划优化重复计算。 5. **最大子段和问题**: 要求找到具有最大和的连续子数组，使用Kadane算法，时间复杂度为O(mn)。 6. **0-1背包问题**: 一个经典的组合优化问题，涉及物品选择策略，其最坏情况下的时间复杂度为O(min{nc,2n,n^(1.44)})，通过贪心策略或动态规划求解。 7. **最优排序二叉树 (第二次提及)**: 这里可能是两种不同的最优排序策略，一次是基于频率的，另一次可能是其他形式的排序，具体取决于上下文。 8. **最优合并问题**: 涉及数据结构的合并操作，比如合并两个有序数组，时间复杂度为O(nlogn)，通常使用归并排序的思想。 这份教程深入剖析了动态规划在这些问题上的应用，通过实例演示了如何识别问题的最优子结构和重叠子问题，以及如何利用动态规划技巧（如记忆化搜索）来高效求解。每个问题都包含了问题分析、递推式、关键步骤和可能的空间优化策略，是学习和理解动态规划的重要参考资料。