动态规划详解：从入门到进阶

"动态规划学习笔记，适用于ACM新手入门，内容包括动态规划的基本概念、种类以及最长公共子序列和最长不下降子序列的算法实现。" 动态规划是一种强大的解决优化问题的方法，尤其在计算机科学和算法竞赛（如ACM）中广泛应用。它基于最优子结构和重叠子问题两大原则，通过将复杂问题分解成较小的子问题来求解。动态规划的核心在于填表，即通过构建表格存储子问题的解，逐步递推得到原问题的最优解。 ### 动态规划认知 动态规划的关键在于找到合适的子问题，并定义状态转移方程。一旦问题满足最优子结构（即局部最优解能组合成全局最优解）和重叠子问题（同一个子问题被多次求解），就可以考虑使用动态规划。 ### dp种类 - **简单基础DP**: 基础的动态规划问题，通常涉及单个变量的状态转移。 - **划分型DP**: 问题可以分为相互独立的部分，每个部分都有自己的子问题。 - **区间DP**: 涉及到区间或连续子序列的问题，例如区间最值问题。 - **概率DP**: 当决策过程中存在不确定性时，需要用到概率计算。 - **进阶DP**: 包括树形DP、状态压缩（状压DP）和数位DP等，处理更复杂的数据结构和问题特性。 ### 最长公共子序列 (Longest Common Subsequence, LCS) LCS 是寻找两个序列中最长的不相交子序列，使得这子序列同时存在于两个原始序列中。在动态规划中，我们通常使用二维数组 `lcs` 来存储子问题的解。初始化数组后，通过比较两个序列的对应元素是否相等来更新 `lcs` 数组。如果 `a[i-1] == b[j-1]`，那么 `lcs[i][j] = lcs[i-1][j-1] + 1`，表示公共子序列的长度增加1。在不相等的情况下，取 `lcs[i][j-1]` 和 `lcs[i-1][j]` 的较大值，确保在无法同时包含 `a[i]` 和 `b[j]` 时选择当前最优解。 ### 最长不下降子序列 (Longest Increasing Subsequence, LIS) LIS 问题寻找一个序列中所有子序列的最长子序列，该子序列是严格递增的。这里我们可以定义 `dp[i]` 表示长度为 `i` 的递增子序列的末尾元素的最大值。初始状态 `dp[1] = num[1]`，然后通过遍历序列，对于每个元素 `num[j]`，更新 `dp` 数组，如果 `num[j]` 大于 `dp[len]`，则更新 `dp[len+1] = num[j]` 并增加 `len`。这样，`dp` 数组的最后一个元素就是最长不下降子序列的长度。 在实际编程中，除了理解和掌握这些基本概念，还需要不断地练习和实践，才能灵活运用动态规划解决各种复杂问题。动态规划不仅限于上述示例，它还可以应用于许多其他领域，如网络流、背包问题、图论等。通过深入学习和实践，你可以逐渐成为一个动态规划的大师。