★ FEATURED ARTICLE 文档教程【免费下载链接】learnxinyminutes-docsCode documentation written as code! How novel and totally my idea!项目地址https://gitcode.com/gh_mirrors/le/learnxinyminutes-docs点击查看免费下载本篇基于 learnxinyminutes-docs 仓库中的意大利语版算法文档 it/dynamic-programming.md 展开并以英文原版 dynamic-programming.md、俄语版 ru/dynamic-programming.md 交叉印证。它系统讲解动态规划Dynamic Programming简称 DP的核心思想、Top-Down 与 Bottom-Up 两种解题范式并以最长递增子序列Longest Increasing SubsequenceLIS为实战案例给出可运行的代码与复杂度分析。读完本文你将掌握动态规划问题的识别方法、记忆化与表格法的实现技巧以及 LIS、背包、Floyd Warshall、最长公共子序列等经典 DP 问题的解题骨架。引言动态规划到底在解决什么动态规划是一种用于解决特定类别问题的强大技术。其思想非常朴素如果你已经用给定的输入解决了一个问题就把结果保存下来供将来参考从而避免对同一个问题重复求解。原文档用一句名言概括了这一哲学Chi non ricorda il passato è condannato a ripeterlo那些不能记住过去的人注定要重蹈覆辙在 learnxinyminutes-docs 仓库中这篇文章被归类于Algorithms Data Structures算法与数据结构类别参见 CONTRIBUTING.md 中关于category字段的约定与仓库内大量代码即文档的语言教程不同它讲解的是一种跨语言的算法思想因此不绑定任何具体编程语言而是用伪代码与数学描述来呈现。从工程视角看DP 之所以高效是因为它精准命中了暴力递归的两大痛点重叠子问题Overlapping Subproblems同一个子问题在递归树中被反复计算多次最优子结构Optimal Substructure全局最优解可以由子问题的最优解组合而成。凡是同时具备这两个特征的问题都值得尝试用 DP 求解。原文档后续给出的 LIS、背包、Floyd Warshall、LCS 全部满足这两个性质。两种解题范式Top-Down 与 Bottom-Up原文档将 DP 的求解方式划分为两条路径二者的差别在于子问题的求解顺序与结果的存储方式。1. Top-Down自顶向下记忆化Memoization从原问题出发将其逐步拆解为子问题如果发现某个子问题已经求解过直接返回已保存的答案如果尚未求解则求解它并把结果保存起来。这种方式通常最容易构思、也最符合人的直觉代码形态上往往就是带缓存的递归。它被称为记忆化Memoization缓存通常是一个数组或哈希表键为子问题的输入状态值为已计算的答案。2. Bottom-Up自底向上表格法Tabulation先分析问题弄清子问题之间的依赖顺序然后从最平凡trivial的子问题开始逐级向上求解直到原问题。这个过程中可以保证在求解任何问题之前它所依赖的所有子问题都已经被解决。这种方式才是严格意义上的动态规划通常用循环 数组DP 表实现没有递归调用栈开销。两种方式的对比可归纳为下表维度Top-Down记忆化Bottom-Up表格法方向从原问题递归下探到最小子问题从最小子问题迭代上升到原问题实现形态递归 缓存Memoization循环 DP 表Tabulation直觉性高贴近暴力递归思路低需要先推导状态转移顺序性能有递归调用栈开销可能只计算真正需要的子问题无递归开销但可能计算所有子问题适用场景状态空间稀疏、依赖关系复杂状态空间紧凑、子问题全覆盖补充一点原文档的措辞细节在意大利语原文中这两种方式分别被表述为Top-Down与Bottom-Up并明确指出后者garantito che i sottoproblemi vengono risolti prima di risolvere il problema保证子问题先于问题被求解。这正是 Bottom-Up 正确性的根基——依赖顺序由人工显式编排天然避免重复计算。实战案例最长递增子序列Longest Increasing Subsequence这是原文档的核心示例也是 DP 入门最经典的题目之一。问题定义给定一个序列S {a1, a2, a3, a4, ..., an-1, an}我们需要找出最长的递增子序列即最长的子集使得子集中任意j i的元素都满足aj ai。注意子序列不要求元素在原始序列中连续只要求保持原有相对顺序。状态设计与递推关系原文档给出的状态定义为LSi表示以ai作为最后一个元素的最长递增子序列长度。于是初始化每个LSi初始化为 1因为ai自身单独就构成一个长度为 1 的递增子序列此时它既是第一个元素也是最后一个元素递推对所有满足j i且aj ai的j找到其中最大的LSj令LSi LSj 1答案整个序列的最长递增子序列长度就是所有LSi中的最大值。该算法的朴素时间复杂度为O(n²)外层遍历每个i内层扫描所有j i。原文档伪代码完整继承原文档给出的求 LIS 长度的伪代码如下for i0 to n-1 LS[i]1 for j0 to i-1 if (a[i] a[j] and LS[i]LS[j]) LS[i] LS[j]1 for i0 to n-1 if (largest LS[i])其中第一个双层循环完成状态填充LS[i]在满足a[i] a[j]时不断尝试用LS[j]1刷新自己第二个单层循环用于扫描出全局最大值largest。可运行的 Python 实现为了让伪代码真正落地这里给出等价的完整 Python 实现并补全原文档伪代码中省略的收尾逻辑def lis_length(seq): n len(seq) if n 0: return 0 # LS[i]以 seq[i] 结尾的最长递增子序列长度初始均为 1 ls [1] * n for i in range(n): for j in range(i): if seq[i] seq[j] and ls[i] ls[j] 1: ls[i] ls[j] 1 largest 0 for i in range(n): if largest ls[i]: largest ls[i] return largest print(lis_length([3, 1, 4, 1, 5, 9, 2, 6, 5])) # 输出 4如 1, 4, 5, 9若还想还原出具体的子序列本身而不只是长度可以额外维护一个predecessor数组记录每个LS[i]是由哪个j转移而来最后从最大LS对应的下标沿前驱链回溯。这正是原文档所提示的优化方向。复杂度与优化方向时间复杂度O(n²)来源于双重循环空间复杂度O(n)仅需一维数组LS。原文档明确指出这一复杂度可以通过使用更好的数据结构来降低例如保存largest_sequences_so_far迄今为止最长的序列变量及其下标或改用二分查找维护各长度递增子序列的最小结尾元素经典的 patience sorting 思路即可将时间复杂度优化到O(n log n)。需要说明的是O(n log n) 的版本属于对原文档思想的进阶延伸本仓库的 it/dynamic-programming.md 原文只给出 O(n²) 伪代码读者可在此基础上自行推导。延伸有向无环图中的最长路径原文档在 LIS 之后给出了一条重要提示类似的概念可以直接应用于求解有向无环图DAG中的最长路径。事实上LIS 可以看作 DAG 最长路径的特例——把序列中每个元素看作节点若i j且ai aj则连一条有向边LIS 正是这个 DAG 上的最长路径而在一般 DAG 上同样可以先做拓扑排序再按拓扑序递推到达每个节点的最长路径长度。理解这一联系有助于把 DP 思想迁移到图算法场景。其他经典 DP 问题速览原文档在末尾列出三个著名的 DP 问题原文档附带的为外部教程链接此处不再列出外链仅给出问题本身的核心递推骨架供读者对照练习1. Floyd Warshall 算法全源最短路径求图中所有节点对之间的最短路径。核心状态为dp[k][i][j]只允许经过前k个中间节点时i到j的最短距离。递推关系dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])实现时通常复用二维数组将k作为最外层循环复杂度 O(V³)。2. 整数背包问题Integer Knapsack给定n件物品每件有重量与价值和一个容量为C的背包求能装入的最大总价值。核心状态为dp[i][w]只考虑前i件物品、容量为w时的最优价值。递推关系dp[i][w] max(dp[i-1][w], dp[i-1][w - weight[i]] value[i])即不取第 i 件与取第 i 件二者取优若背包容量允许还可进一步压缩为一维滚动数组。它是 0/1 背包与完全背包等一系列变体的母题。3. 最长公共子序列Longest Common SubsequenceLCS给定两个序列求它们的最长公共子序列长度。核心状态为dp[i][j]A[0..i-1]与B[0..j-1]的 LCS 长度。递推关系若 A[i-1] B[j-1]dp[i][j] dp[i-1][j-1] 1 否则dp[i][j] max(dp[i-1][j], dp[i][j-1])这是典型的二维表格 DP复杂度 O(n·m)广泛用于文本比对、基因序列分析等场景。这三个问题与 LIS 共同构成了 DP 入门的高频题库掌握了它们的状态定义与转移方程写法就基本掌握了 DP 的建模套路。在仓库中继续深入learnxinyminutes-docs 以代码即文档的形式为每种语言/主题维护独立 Markdown 文件动态规划主题在仓库内存在多个语言版本可对照阅读意大利语原文it/dynamic-programming.md英文原版dynamic-programming.md内容最完整且附有 MIT 6.006、TopCoder、GeeksForGeeks 等进阶资源清单俄语版ru/dynamic-programming.md另外仓库中的 it/gdscript.md 在讲解 GDScript 类型系统时也提到stiamo usando la potenza della programmazione dinamica我们在利用动态规划的力量可以作为一个跨语言应用的趣味注脚。若你希望参与这类算法文档的维护仓库的 CONTRIBUTING.md 给出了明确的格式规范frontmatter 元数据、80 字符行宽、代码示例优先等欢迎以 pull request 形式贡献。结语动态规划的全部精髓可以用一句话概括把已经算过的答案存起来让每个子问题只算一次。掌握 Top-Down记忆化与 Bottom-Up表格法两条路径再通过 LIS、背包、Floyd Warshall、LCS 等经典题目反复练习状态定义与转移方程的推导就能在算法竞赛与工程优化中熟练运用这一技术。从 it/dynamic-programming.md 出发你可以继续在仓库的英文原版与俄语版中获取更丰富的进阶资源把 DP 从看得懂推进到写得对。赞分享文档教程【免费下载链接】learnxinyminutes-docsCode documentation written as code! How novel and totally my idea!项目地址https://gitcode.com/gh_mirrors/le/learnxinyminutes-docs点击查看免费下载相关推荐Learn X in Y Minutes 动态规划指南记忆化、自底向上 DP 与最长上升子序列实战解析Learn X in Y Minutes 动态规划指南记忆化、自底向上 DP 与最长上升子序列实战解析 动态规划Dynamic ProgrammingDP文档教程OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南OptiScaler任何游戏都能用上 FSR4 和帧生成吗超分替换完全指南 OptiScaler 是一款开源的超分辨率替换工具把游戏里原生的 DLSS /图形学游戏开发Learn X in Y minutes 系列LiveScript 函数式 JavaScript 编译语言完整实战指南Learn X in Y minutes 系列LiveScript 函数式 JavaScript 编译语言完整实战指南 本指南基于 learnxinyminu文档教程上一篇基于 Rerun Gradio SAM 2 的交互式 3D 标注应用annotation_gradio 示例深度解析下一篇Differentiable Block Worlds 论文可视化走读用 Rerun 观察超二次曲面 3D 场景分解的优化过程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
)
