1. 项目概述从一道经典题看透动态规划的核心思想最近在洛谷上刷题又看到了这道经典的B3637最长上升子序列。这道题被很多朋友称为“动规板子题”但说实话我第一次接触动态规划DP时就是被这类“板子题”给绕晕的。题目描述很简单给你一个整数序列让你找出其中最长的、严格递增的子序列的长度。比如序列[1, 3, 2, 4, 5]它的最长上升子序列LIS可以是[1, 3, 4, 5]或[1, 2, 4, 5]长度都是4。问题看似直观但如何让计算机高效地求解里面蕴含的正是动态规划最精髓的“状态定义”与“状态转移”思想。这道题的价值远不止于AC。它像一把钥匙能帮你打开动态规划这扇大门。很多更复杂的问题比如最长公共子序列、编辑距离、最大子数组和其底层逻辑和思考方式都与LIS问题一脉相承。如果你正在准备信息学竞赛、求职算法面试或者单纯想提升自己的编程思维能力彻底吃透LIS问题都是至关重要的一步。本文将带你从最朴素的暴力思路开始一步步推导出最优的动态规划解法并附上可直接提交的C代码实现。我们不止讲“怎么做”更要讲清楚“为什么这么做”以及我在反复刷题中积累的那些容易踩坑的细节和调试技巧。2. 问题核心与暴力解法的局限性在深入动态规划之前我们必须先明确问题到底是什么以及最直接但低效的解决方法为何行不通。这能帮助我们更好地理解DP优化的必要性。2.1 最长上升子序列的严格定义给定一个长度为n的序列a[1], a[2], ..., a[n]。一个子序列是通过从原序列中删除一些也可以不删除元素但不改变剩余元素的相对顺序而得到的新序列。所谓“上升子序列”要求这个子序列中的元素是严格递增的即对于子序列中任意两个相邻的元素后一个必须大于前一个。我们的目标是找到所有可能的上升子序列中长度最长的那个并输出其长度。以洛谷B3637的样例1 3 2 4 5为例合法的上升子序列有[1],[3],[2],[4],[5],[1, 3],[1, 2],[1, 4],[1, 5],[3, 4],[3, 5],[2, 4],[2, 5],[4, 5],[1, 3, 4],[1, 3, 5],[1, 2, 4],[1, 2, 5],[3, 4, 5],[2, 4, 5],[1, 3, 4, 5],[1, 2, 4, 5]。其中最长的长度是4对应的子序列如[1, 3, 4, 5]。注意题目要求是“严格递增”这意味着[1, 1]或[2, 2]这样的序列是不符合要求的。在有些变体问题中可能会允许“非严格递增”即a[i] a[i1]但本题明确是严格递增写代码时判断条件要用而非。2.2 枚举所有子序列的暴力思路及其瓶颈最直观的想法是既然要找最长的那我干脆把所有可能的子序列都列出来然后一个个检查它是不是上升的最后记录下最大长度。一个长度为n的序列其子序列有多少个呢每个元素都有“选”或“不选”两种可能因此总共有2^n个子序列包括空序列。生成所有子序列通常用递归或位运算枚举。// 暴力枚举思路的伪代码仅用于理解不可行 int bruteForceLIS(vectorint a) { int n a.size(); int maxLen 0; // 枚举所有子序列通过枚举所有掩码 for (int mask 0; mask (1 n); mask) { vectorint subseq; for (int i 0; i n; i) { if (mask (1 i)) { subseq.push_back(a[i]); } } // 检查子序列是否严格递增 bool isIncreasing true; for (int j 1; j subseq.size(); j) { if (subseq[j] subseq[j-1]) { isIncreasing false; break; } } if (isIncreasing) { maxLen max(maxLen, (int)subseq.size()); } } return maxLen; }为什么这个方法不行计算一下时间复杂度外层循环2^n次内层需要O(n)时间生成和检查子序列总时间复杂度是O(n * 2^n)。当n5000时2^5000是一个天文数字完全无法在1秒典型的时间限制内完成。实际上n超过30这种方法就基本不可行了。因此我们必须寻找更高效的算法这就是动态规划登场的时候。3. 动态规划解法的核心思路拆解动态规划的精髓在于“利用已经计算过的子问题答案来求解当前问题”避免重复计算。对于LIS问题我们需要设计合适的状态表示和状态转移方程。3.1 状态定义dp[i]到底代表什么这是理解DP最关键的一步也是最容易想错的一步。一个常见的错误定义是dp[i]表示“以第i个元素结尾的上升子序列的集合”。这太模糊了计算机无法处理一个“集合”。我们必须用一个具体的数值来描述状态。正确的定义是dp[i]表示以序列中第i个元素a[i]作为最后一个元素的、所有上升子序列中最长的那个的长度。举个例子对于序列a [1, 3, 2, 4, 5]dp[1]以a[1]1结尾的上升子序列只有[1]本身所以dp[1] 1。dp[2]以a[2]3结尾的上升子序列有[3]和[1, 3]。最长的是[1, 3]长度为2所以dp[2] 2。dp[3]以a[3]2结尾的上升子序列有[2]和[1, 2]。最长的是[1, 2]长度为2所以dp[3] 2。dp[4]以a[4]4结尾的上升子序列有很多如[4],[1,4],[3,4],[2,4],[1,3,4],[1,2,4]。其中最长的[1,3,4]或[1,2,4]长度是3所以dp[4] 3。dp[5]同理以5结尾的最长上升子序列是[1,3,4,5]或[1,2,4,5]长度为4所以dp[5] 4。定义完dp[i]后整个序列的最长上升子序列长度即最终答案就是所有dp[i]中的最大值即max(dp[1], dp[2], ..., dp[n])。因为最长上升子序列必然以序列中的某个元素结尾。3.2 状态转移方程如何从已知推导未知现在我们知道dp[i]是什么了接下来要解决怎么算。动态规划要求我们能用“更小的”或“已经算好的”子问题的解来求当前问题的解。对于dp[i]我们思考以a[i]结尾的最长上升子序列它的前一个元素可能是谁这个前一个元素必须是原序列中在i之前j i的某个位置j上的元素a[j]并且要满足a[j] a[i]保证上升。那么以a[i]结尾的最长上升子序列就可以看作是在某个以a[j]结尾的最长上升子序列后面再接上a[i]形成的。这个新序列的长度就是dp[j] 1。由于j可以是所有满足j i且a[j] a[i]的位置我们要找到那个能使dp[j] 1最大的j。这样得到的才是以a[i]结尾的“最长”上升子序列。因此状态转移方程可以写为dp[i] max(dp[j] 1)其中j满足1 j i且a[j] a[i]。如果不存在这样的j即a[i]前面的所有元素都大于或等于它那么以a[i]结尾的上升子序列就只能是它自己长度为1。所以我们需要给dp[i]一个初始值dp[i] 1每个元素本身至少可以构成一个长度为1的上升子序列。然后我们遍历所有j i如果a[j] a[i]就尝试用dp[j] 1来更新dp[i]的最大值。3.3 算法流程与时间复杂度分析基于以上分析我们可以梳理出完整的算法步骤初始化创建一个长度为n1的数组dp为了下标从1开始方便并将所有dp[i]初始化为1。递推计算外层循环i从2遍历到n计算每一个dp[i]。内层循环j从1遍历到i-1。在内层循环中判断if (a[j] a[i])如果成立则更新dp[i] max(dp[i], dp[j] 1)。获取答案遍历整个dp数组找到其中的最大值即为整个序列的最长上升子序列长度。时间复杂度分析 外层循环n次内层循环平均大约n/2次所以总的时间复杂度是O(n^2)。对于本题n 5000n^2最大是2500万在C中通常可以在1秒内完成是可行的。空间复杂度我们只需要O(n)的额外空间来存储dp数组和原序列。4. C代码实现与逐行解析理解了原理代码实现就水到渠成了。下面给出针对洛谷B3637的完整C题解代码并附上详细注释。#include iostream #include vector #include algorithm // 用于max函数 using namespace std; int main() { int n; cin n; vectorint a(n 1); // 让下标从1开始符合题目描述和思维习惯 vectorint dp(n 1, 1); // dp数组同时初始化为1 // 读入序列 for (int i 1; i n; i) { cin a[i]; } // 核心动态规划过程 for (int i 2; i n; i) { // 计算每一个dp[i] for (int j 1; j i; j) { // 遍历i之前的所有元素 if (a[j] a[i]) { // 满足上升条件 // 尝试用以a[j]结尾的LIS加上a[i]来更新dp[i] dp[i] max(dp[i], dp[j] 1); } } } // 找出dp数组中的最大值即为答案 int ans 0; for (int i 1; i n; i) { ans max(ans, dp[i]); } cout ans endl; return 0; }代码逐行解析与关键点输入与容器选择vectorint a(n 1);我们让数组下标从1开始这样更直观地对应第1个到第n个元素避免在思考dp[i]和a[i]关系时进行繁琐的下标转换。这是处理竞赛题时的一个常用技巧。vectorint dp(n 1, 1);在声明dp数组时直接通过构造函数将其所有元素初始化为1。这等价于dp[i] 1的初始化步骤更加简洁。核心双重循环外层i从2开始因为dp[1]已经确定是1无需计算。内层j遍历1到i-1这正是状态转移方程j i的体现。if (a[j] a[i])是“严格递增”的关键判断。如果题目变成“非严格递增”这里需要改为。dp[i] max(dp[i], dp[j] 1);是状态转移的核心。dp[i]的初始值是1内层循环会尝试所有可能的j用更大的dp[j] 1来更新它。答案获取计算完所有dp[i]后最长上升子序列的长度就分散在这个数组中。我们只需要遍历一次用max函数找出最大值即可。输出直接输出ans。实操心得数组下标从1开始在算法竞赛和动态规划问题中我强烈建议让数组下标从1开始尤其是当状态定义与元素序号直接相关时比如这里的“以第i个元素结尾”。这能极大减少思维负担和调试时因下标错误导致的bug。虽然这会浪费a[0]和dp[0]这个位置但对于n5000的规模来说这点空间开销微不足道。5. 算法优化O(n log n)的贪心二分法O(n^2)的解法对于n5000是足够的但如果数据范围扩大到n 10^5甚至更大呢O(n^2)就会超时。这时就需要更优的O(n log n)解法。理解这种解法对深入掌握LIS问题大有裨益。5.1 优化思路维护一个“潜力序列”O(n log n)算法的核心思想不再是直接计算长度而是维护一个数组low或常命名为d。low[len]的含义是所有长度为len的上升子序列中结尾元素的最小值。为什么维护这个值因为对于相同长度的上升子序列结尾元素越小未来它后面能接上更多元素变得更长的潜力就越大。我们希望通过不断用更小的结尾元素去替换low数组中的值使得整个数组保持一个缓慢增长的状态从而更容易扩展出更长的子序列。5.2 算法步骤详解初始化low数组为空。遍历原序列的每个元素a[i] a. 如果a[i]大于low数组的最后一个元素即当前找到的最长上升子序列的结尾说明我们可以把a[i]直接接在后面得到一个更长的上升子序列。执行low.push_back(a[i])。 b. 否则说明a[i]不能直接延长当前的最长子序列。但是它可能可以用来更新某个长度的子序列的结尾使其变得更小、潜力更大。我们在low数组中找到第一个大于或等于a[i]的元素的位置使用二分查找然后用a[i]替换掉那个位置的元素。遍历结束后low数组的长度就是最长上升子序列的长度。关键点low数组本身不一定是一个合法的上升子序列因为其中的元素是通过替换得到的可能来自原序列的不同位置但它的长度一定等于最长上升子序列的长度。5.3O(n log n)解法C实现#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } vectorint low; // 维护的潜力序列 for (int i 0; i n; i) { // 在low中找到第一个 a[i] 的元素位置 auto it lower_bound(low.begin(), low.end(), a[i]); if (it low.end()) { // 如果没找到说明a[i]比所有结尾都大可以延长子序列 low.push_back(a[i]); } else { // 找到了用a[i]替换那个位置的元素使该长度的结尾更小 *it a[i]; } } // low的长度即为LIS长度 cout low.size() endl; return 0; }代码解析lower_bound(begin, end, val)是C标准库函数在有序区间[begin, end)中返回第一个大于或等于val的元素的迭代器。这正是我们需要的“找到第一个 a[i] 的位置”。如果it low.end()说明a[i]比low中所有元素都大可以接在后面形成更长的序列。否则用a[i]替换*it。因为a[i] *it替换后能保证该长度下的结尾元素变得更小但不改变low数组的递增性质。该算法只遍历一次序列a每次操作二分查找可能的替换是O(log n)所以总复杂度O(n log n)。注意事项关于lower_bound与upper_bound在这个算法中必须使用lower_bound找第一个大于等于a[i]的位置。如果使用upper_bound找第一个大于a[i]的位置对于序列中有重复元素的情况可能会得到错误的结果。因为我们要维护的是严格递增子序列当遇到一个和low中某个元素相等的值时我们不应该延长序列因为不满足严格递增但可以用它替换掉那个相等的元素使结尾不变但逻辑正确。lower_bound在遇到相等值时返回该位置正好用于替换。6. 常见问题与调试技巧实录即便理解了算法亲手实现时还是会遇到各种问题。下面是我在多次解答和教学中总结的常见坑点及解决方法。6.1 典型错误与排查清单问题现象可能原因解决方案输出结果总是1dp数组没有正确初始化或者状态转移条件写错如a[j] a[i]写成了a[j] a[i]不这里应该是。更常见的是内层循环j的范围错误或者dp[i]的更新逻辑写在了if条件之外。1. 确认dp数组所有元素初始化为1。2. 在状态转移的if语句内部打印i, j, a[i], a[j], dp[i], dp[j]的值观察是否在条件满足时执行了更新。3. 检查内层循环是否为for (int j 1; j i; j)。样例通过提交后部分WAWrong Answer1. 没有处理n0或n1的边界情况虽然本题n1。2. 数组下标越界。如果从0开始存储要确保dp[0]也被正确初始化且循环范围是[0, n-1]。3. 题目理解错误将“严格递增”误实现为“非严格递增”。1. 仔细阅读题目数据范围说明。2. 使用vector并指定大小避免原生数组越界。3.最有效的调试方法自己构造小规模极端数据测试。例如- 降序序列[5,4,3,2,1]答案应为1。- 升序序列[1,2,3,4,5]答案应为5。- 有重复元素的序列[1,2,2,3,4]答案应为4[1,2,3,4]注意不能选两个2。使用O(n log n)解法结果错误1. 错误使用了upper_bound而不是lower_bound。2.low数组的更新逻辑错误例如在a[i]等于某个结尾时仍然执行了push_back。3. 初始序列a的下标处理混乱。1. 牢记严格递增LIS用lower_bound。2. 手动模拟算法过程。对于[2,1,5,3,4]- i0, a2, low[] - push - low[2]- i1, a1, lower_bound找到2 - 替换 - low[1]- i2, a5, low[1] - push - low[1,5]- i3, a3, lower_bound找到5 - 替换 - low[1,3]- i4, a4, low[1,3] - push - low[1,3,4]最终长度3正确。程序运行超时TLE对于n5000O(n^2)算法理应不超时。如果超时可能是1. 使用了cin/cout而没有关闭同步流在输入量大时效率低下。2. 在循环中进行了不必要的复杂操作。1. 在main函数开头添加ios::sync_with_stdio(false); cin.tie(nullptr);来加速cin/cout。2. 或者使用scanf/printf进行输入输出。3. 检查是否存在死循环或冗余计算。6.2 调试与验证技巧打印DP表在开发O(n^2)算法时最直观的调试方法就是打印出整个dp数组。对于样例[1,3,2,4,5]你的dp数组应该是[1, 2, 2, 3, 4]下标从1开始。如果结果不符立刻就能定位到第一个出错的位置i。小数据模拟不要依赖在线判题系统的反馈。在本地用纸笔或注释模拟算法对一个小序列比如3-5个元素的执行过程。这是理解算法和发现逻辑错误最有效的方法。对拍如果你实现了两种解法如O(n^2)和O(n log n)可以写一个随机数据生成器生成大量随机序列分别用两种算法运行并对比结果。如果结果不一致就能找到反例进而定位bug。注意输入输出格式洛谷题目通常要求严格匹配格式。确保你的程序只输出一个整数答案不要有多余的空格或换行。对于n0的情况如果题目允许要确保程序有合理的输出通常是0。7. 从LIS问题延伸的思考与练习彻底掌握基础LIS解法后你可以尝试解决一些变种问题这能极大地加深对动态规划思想的理解。输出最长上升子序列本身而不仅仅是长度这需要我们在动态规划过程中记录“转移路径”。通常用另一个数组pre[i]来记录在以a[i]结尾的最长上升子序列中a[i]的前一个元素的下标是什么。计算完dp数组后先找到使dp[i]最大的i即结尾位置然后通过pre数组不断向前回溯即可还原出整个序列。注意回溯出来的序列是逆序的需要反转。最长不下降子序列非严格递增只需将状态转移条件中的a[j] a[i]改为a[j] a[i]即可。对于O(n log n)的算法则需要使用upper_bound找第一个大于a[i]的位置进行替换因为相等元素可以接在后面。二维LIS问题如“俄罗斯套娃信封问题”给定一些信封的宽高(w, h)当另一个信封的宽和高都大于某个信封时可以套进去。问最多能套多少层。一个经典的技巧是先对宽度w进行升序排序如果w相同则按高度h降序排序。然后在排序后的序列中对高度h求LIS得到的就是答案。排序后宽度维度已经满足要求只需高度递增即可且同宽度下高度降序保证了同宽度的信封不会互相嵌套。LIS与二分查找的深入理解O(n log n)的解法本质是一种“贪心”策略其正确性证明需要理解low数组的单调性以及替换操作不会影响最终最大长度。多找一些证明资料看看对思维提升很有帮助。最长上升子序列问题就像动态规划领域的一块基石。理解它不仅能帮你解决一类具体问题更能让你体会到如何将一个大问题分解为重叠的子问题并用数组存储这些子问题的解以避免重复计算。这种“状态”和“转移”的思维模式是解决无数更复杂DP问题的钥匙。下次当你遇到一个看似棘手的新问题时不妨问问自己这个问题的最优解是否可以通过一系列子问题的最优解组合而来