文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载本文围绕《算法导论》Introduction to Algorithms第 15.4 节最长公共子序列Longest Common Subsequence, LCS的六道习题展开系统讲解 LCS 长度的计算、路径重建、记忆化递归优化、空间压缩以及最长单调递增子序列LIS的 O(n²) 与 O(n lg n) 两种解法。全文以仓库中的 15.4.md 为骨架结合 lincrs.cpp 源码给出可运行实现读者学完后既能完整推导 LCS/LIS 的递推关系也能写出空间最优的工程级代码。一、问题背景从动态规划最优子结构谈起LCS 问题要求给定两个序列 X x1, x2, ..., xm与 Y y1, y2, ..., yn找出同时是二者子序列的最长序列。其核心递推式为若x[i] y[j]则c[i,j] c[i-1,j-1] 1否则c[i,j] max(c[i-1,j], c[i,j-1])。其中c[i,j]表示X[1..i]与Y[1..j]的 LCS 长度。15.4 节的习题从基础实例计算、路径回溯、记忆化、空间优化到复杂度升级层层递进下面逐题展开。二、Exercise 15.4-1手算一组具体序列的 LCS确定序列1, 0, 0, 1, 0, 1, 0, 1与0, 1, 0, 1, 1, 0, 1, 1, 0的一个 LCS。15.4.md 给出的答案为1, 0, 0, 1, 1, 0或等价地1, 0, 1, 0, 1, 0。验证思路按递推式填一张 m×n 的表从c[1,1]逐项计算到c[m,n]。题目给定的两个序列长度分别为 8 与 9LCS 长度为 6。注意 LCS 不唯一——多个长度相同的公共子序列都是合法答案这正说明一个 LCS而非唯一 LCS。读者可自行按递推式填表核对两个候选答案都同时是两个序列的子序列且长度均为 6满足最优性。三、Exercise 15.4-2不使用 b 表在 O(mn) 内重建 LCS标准教材用 b 表记录每个c[i,j]的取值方向左上 / 上 / 左。本习题要求只凭 c 表重建 LCSPRINT_LCS(c, x, y, i, j) if i 0 || j 0 return if x[i] y[j] PRINT_LCS(c, x, y, i-1, j-1) print x[i] elif c[i-1, j] c[i, j-1] PRINT_LCS(c, x, y, i-1, j) else PRINT_LCS(c, x, y, i, j-1)为什么成立当x[i] y[j]时该字符必然属于某个 LCS直接沿(i-1, j-1)回溯当二者不等时c[i,j]必然继承自c[i-1,j]与c[i,j-1]中的较大者相等时任意选择此处约定优先向上i-1因此仅凭 c 表的数值即可判断移动方向无需额外的 b 表。每步递归要么i减一、要么j减一最多经过 mn 次调用所以总时间为 O(mn)匹配习题要求的复杂度。四、Exercise 15.4-3LCS 的记忆化Memoized版本O(mn) 时间自上而下的递归写法直接照搬递推式会有大量重叠子问题记忆化通过查表 - 未计算则递归求值并回填避免重复LCS-LENGTH(X, Y) m ← length[X] n ← length[Y] for i ← 1 to m do for j ← 1 to n do c[i,j] ← -1 end for end for return LOOKUP-LENGTH(X, Y, m, n) LOOKUP-LENGTH(X, Y, i, j) if c[i,j] -1 then return c[i,j] end if if i 0 or j 0 then c[i,j] ← 0 else if X[i] Y[j] then c[i,j] ← LOOKUP-LENGTH(X, Y, i-1, j-1) 1 else c[i,j] ← max(LOOKUP-LENGTH(X, Y, i, j-1), LOOKUP-LENGTH(X, Y, i-1, j)) end if end if return c[i,j]实现要点先用 -1 初始化 c 表作为尚未计算的哨兵值LCS 长度非负-1 不会与合法结果冲突每个子问题(i, j)至多被计算一次每次计算是常数时间因此总复杂度为 O(mn)与自底向上填表同阶边界条件i 0 或 j 0直接返回 0对应空序列的 LCS 长度。记忆化与自底向上bottom-up在最优子结构相同的前提下互为表里前者天然保留递归语义、只计算真正需要的子问题适合对表格局部求解的场景。五、Exercise 15.4-4把 c 表空间压缩到 2·min(m,n) 乃至 min(m,n)计算c[i,j]只依赖三个邻居c[i-1,j-1]、c[i,j-1]、c[i-1,j]。这意味着整张表不需要常驻内存只需滚动保存最近两行因为求解一个项 c[i,j]只会用到 c[i-1,j-1]、c[i,j-1]、c[i-1,j]。所以运行时刻我们只需要保存上面一行的状态和当前行的状态即可。再令 X、Y 这两个字符串中短的那一个放到 index j所以可以用 2 · min(m, n) 的空间运行算法。原文档中文说明的关键工程细节2 · min(m, n) 方案保留上一行 当前行两个一维数组即可完成整轮填表。为保证行数取较小者把 X、Y 中较短的那个序列映射到列方向index j于是行数为 min(m, n)总占用 2 · min(m, n)。min(m, n) 方案更进一步只保留一行。c[i,j-1]当前行左侧本来就在该行中再用一个额外变量保存c[i-1,j-1]上一行左上角。每次更新c[i,j]时先把旧值即c[i-1,j]暂存进这个额外变量供下一列计算c[i-1,j-1]使用——这正是滚动数组rolling array在 LCS 上的经典落地。Since we need only c[i-1,j-1], c[i,j-1], c[i-1,j] to compute c[i,j], we just need to save the previous row and the current row of the dp table. We will maintain the row parallel to the shorter one of the X and Y strings. So we can run the algorithm with 2 · min(m, n) space. In fact, we only need to save only one row. c[i,j-1] is already stored in this row. Then, we use an extra variable to maintain c[i-1,j-1]. Every time c[i,j] is updated, the value of c[i-1,j] is saved into the extra variable because it will be used next time.需要强调的是空间压缩只保留长度信息。若还要重建 LCS 序列本身15.4-2 的 PRINT_LCS 依赖完整 c 表回溯在滚动数组场景下可退化为只求长度或配合额外策略如 Hirschberg 算法折中。工程上需根据要长度还是要序列决定是否接受压缩。六、Exercise 15.4-5LIS 的 O(n²) 算法设计 O(n²) 时间算法求 n 个数的最长单调递增子序列。原文档给出两种方法方法一规约到 LCS将序列 X x1, x2, ..., xn排序得到有序序列 X求 X 与 X 的 LCS即得 X 的最长单调递增子序列。复杂度分析排序 O(n lg n)LCS-LENGTH 为 O(n²)总时间 O(n²)。注意若元素不互异需先做去重或改用严格递增的等价规约。方法二直接 DPLONGEST-INC-SEQUENCE(Arr, n) len [1..n] 为新建数组 for i ← 1 to n len[i] ← 1 // 以 i 结尾的最长递增序列长度 for i ← 2 to n do for j ← 1 to i-1 do if Arr[j] Arr[i] len[i] ← max(len[i], len[j] 1) end if end for end for return len[n]len[i]表示以Arr[i]为结尾的最长递增子序列长度。对每个 i扫描其左侧所有 j凡Arr[j] Arr[i]即可把len[j]的结果延长一位。双层循环使时间达到 O(n²)空间 O(n)。严格递增的判定条件是Arr[j] Arr[i]若需非严格递增则改为。七、Exercise 15.4-6 ★LIS 的 O(n lg n) 算法与仓库实现给出 O(n lg n) 时间算法求最长单调递增子序列。提示长度为 i 的候选子序列的末元素不小于长度为 i-1 的候选子序列的末元素。通过输入序列链接候选子序列。这是本节唯一标记 ★ 的习题也是面试与工程实践中的高频考点。贪心 二分的核心思想是维护数组c其中c[i]表示所有长度为 i 的递增子序列中最小的末尾元素由提示可知c天然是单调递增的因此可以在 O(lg n) 内二分定位第一个大于等于Arr[i]的位置 j用Arr[i]覆盖c[j]得到一个更优的、末尾更小的长度为 j 的子序列若 j 超出当前已知长度则扩展最长长度。仓库中的 lincrs.cpp 即该习题的实现核心代码如下#include iostream using namespace std; int find(int *a, int len, int n) { int left(0), right(len), mid (left right) / 2; while (left right) { if (n a[mid]) left mid 1; else if (n a[mid]) right mid - 1; else return mid; mid (left right) / 2; } return left; } int main() { int n, a[100], c[100], i, j, len; cin n; for (int i 0; i n; i) cin a[i]; c[0] -1; c[1] a[0]; len 1; for (i 1; i n; i) { j find(c, len, a[i]); c[j] a[i]; if (j len) len j; } cout len endl; return 0; }代码要点解读find对单调数组c[1..len]做二分查找返回第一个 ≥ n 的位置即 lower_bound 语义找不到时返回left恰好是应插入的新位置初始化c[0] -1作为哨兵、c[1] a[0]作为首元素len记录当前已知 LIS 长度每处理一个元素做一次二分共 n 次总复杂度 O(n lg n)程序从标准输入读入 n 与 n 个数输出 LIS 长度。可从命令行编译运行验证例如g lincrs.cpp -o lincrs ./lincrs后输入测试数据。该实现只求长度若需输出具体子序列可额外用pre[]数组记录每个位置的前驱在更新c[j]的同时维护链式链接与习题提示通过输入序列链接候选子序列完全对应。八、从习题到工程复杂度与空间对照总结习题问题时间空间关键技巧15.4-1手算 LCS——递推填表、答案不唯一15.4-2重建 LCSO(mn)O(mn)c 表用 c 值判断回溯方向免 b 表15.4-3记忆化 LCSO(mn)O(mn)哨兵值 -1 查表递归15.4-4空间压缩O(mn)2·min(m,n) → min(m,n)滚动数组 额外变量保存左上角15.4-5LISO(n²)O(n)排序规约 LCS或直接 DP15.4-6LISO(n lg n)O(n)贪心维护最小末尾 二分九、延伸动态规划解题模式小结通过 15.4 节的完整练习可以归纳出动态规划解题的通用四步刻画最优子结构LCS 的c[i,j]、LIS 的len[i]都能由更小的子问题递推得到递归定义最优值写出c[i,j]与len[i]的递推方程自底向上或记忆化计算按序填表或带哨兵记忆化递归构造最优解如 15.4-2 的 PRINT_LCS沿 c 表回溯输出序列。结合仓库中 C15-Dynamic-Programming 目录的其他实现如 rodcutting.cpp、Matrix-chain-multiplication.c、Assembly-line-sche.c可以看到同一套递推 填表 回溯范式贯穿整章。读者可将 lincrs.cpp 作为模板进一步练习输出 LIS 序列的变体从而真正把 O(n lg n) 的贪心二分思想内化为可迁移的算法能力。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南 OptiScaler 是一款开源的超分辨率替换工具把游戏里原生的 DLSS /图形学游戏开发如何快速上手CodeLlama-7b-hf5分钟完成安装与推理如何快速上手CodeLlama 7b hf5分钟完成安装与推理 CodeLlama 7b hf是Meta推出的代码生成模型基于70亿参数构建专为代码合成与传统UI自动化测试的技术困境与Midscene.js的视觉驱动架构创新传统UI自动化测试的技术困境与Midscene.js的视觉驱动架构创新 在当今快速迭代的软件开发环境中UI自动化测试面临着前所未有的技术挑战。传统的基于DOM人工智能AI Agent测试GUI 自动化浏览器控制测试智能体上一篇Qwen2.5-Coder-1.5B-Instruct_rai_1.7.1_npu_4K核心特性解析4K上下文与AWQ量化技术下一篇EvilClippy快速入门5分钟学会隐藏VBA宏和代码替换创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考