动态规划

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

前置是循环、切片和递归；每个 package main 在独立模块中保存为 main.go（Go 1.22+），本轮未执行。n、容量、数量都非负，背包数组必须等长、重量为正，跳跃步数非负。矩阵链维度为正；TSP 输入是小规模完整费用矩阵，路径费用小于 inf 且加法不溢出，不把不可达哨兵直接当费用。

要解决的问题	可选方法	选择前确认
递推只依赖前两个结果，或只判断最远可达	斐波那契、爬楼梯、跳跃游戏	前两者可滚动保存状态；跳跃游戏示例是贪心，仅判断能否到达。
每件物品限一次、可无限次或有数量上限	0/1 背包、完全背包、多重背包	0/1 容量倒序，完全背包正序且权重须为正，多重背包拆成二进制组。
比较序列顺序与连续片段	LIS、LCS、最长公共子串	LIS 示例只返回长度；LCS 允许跳过字符，公共子串要求连续且失配归零。
计算修改字符串的最小代价或寻找回文	编辑距离或最长回文子串	编辑距离示例按字节计操作；回文示例用 rune 中心扩展，时间 O(n²)。
答案依赖连续子区间或孩子状态	区间 DP或树形 DP	矩阵链按区间长度计算，时间 O(n³)；树形示例假设输入确为一棵树。
精确求解少量城市的最短回路	状态压缩 DP	状态数 2ⁿ，示例时间 O(n²2ⁿ)，不适合大规模路线规划。

从滚动递推到最远可达判断

斐波那契动态规划

正文、推演与完整示例：斐波那契动态规划。

朴素递归会重复计算大量相同子问题；滚动变量 a、b 分别保存前两个结果。每轮前进一项，既不需要递归栈也不需要完整数组。 时间 O(n)、额外空间 O(1)。

Go 的 int 会在数值过大时溢出，超大 n 应改用 math/big。

爬楼梯

正文、推演与完整示例：爬楼梯。

这里每次允许走 1 或 2 阶；允许更多步长时递推式也要随之改变。

跳跃游戏

正文、推演与完整示例：跳跃游戏。

这个贪心只判断能否到达，不计算最少跳跃次数。

按物品可用次数选择背包转移

0/1 背包

正文、推演与完整示例：0/1 背包。

dp[c] 表示容量不超过 c 时能得到的最大价值。处理某件物品时从大容量倒序更新，确保右侧读取的是“未用过当前物品”的旧状态。 每件物品最多选一次。

若正序更新，同一件物品可能在同轮被选多次，题意就变成完全背包。

完全背包

正文、推演与完整示例：完全背包。

权重必须为正；零重量且正价值的物品会让最优值无界。

多重背包

正文、推演与完整示例：多重背包。

把物品数量按 1、2、4、…及余量拆成若干组，每组视为一件 0/1 物品。例如数量 5 拆为 1、2、2，可以组合出 0 到 5 的取用数量。这比逐件展开减少处理次数，但仍需保证组内重量和价值乘法不溢出。

求递增序列、公共片段、编辑距离与回文

最长递增子序列

正文、推演与完整示例：最长递增子序列。

tails[len−1] 保存某个长度的递增子序列可能达到的最小尾值。遇到新元素时，用二分找到第一个不小于它的位置并替换；这不会直接保存答案序列，但保留了未来延长的最好机会。 时间 O(n log n)。

要重建序列，还需记录前驱下标。

最长公共子序列

正文、推演与完整示例：最长公共子序列。

dp[i][j] 考虑两个字符串各自的前 i、j 个字符。末尾字符相同就接在更短前缀的答案后；不同则分别跳过一侧末尾，取较大者。 时间 O(nm)。

子序列允许不连续，示例按 UTF-8 字节比较；按字符语义处理中文时应改成 rune。

最长公共子串

正文、推演与完整示例：最长公共子串。

示例按字节比较，处理 Unicode 字符时可先转成 rune 切片。

编辑距离

正文、推演与完整示例：编辑距离。

dp[i][j] 是把第一个前缀改成第二个前缀所需的最少操作数。最后字符相同时沿对角线继承，否则在插入、删除和替换三种操作中取最小代价。 二维 DP 时间 O(nm)。

示例按字节计操作；中文字符级编辑距离应把输入转成 rune。

最长回文子串

正文、推演与完整示例：最长回文子串。

回文中心既可能是一个字符，也可能位于两个字符之间，因此每个位置尝试奇数和偶数两类中心。两侧字符相等时继续扩张，并记录最长范围。 中心扩展时间 O(n²)，转为 rune 切片占 O(n) 空间。

示例先转成 rune，能正确处理多字节字符；超大输入可改用线性时间的 Manacher 算法。

按区间或树结构汇总子问题

区间 DP

正文、推演与完整示例：区间 DP。

矩阵链的子问题由连续区间 [l,r] 决定；只有更短区间已经算出，才能枚举切点 k 并组合左右最优代价。按区间长度递增填表满足这一依赖顺序。 目标是矩阵链最少乘法次数。

矩阵维度数组要满足相邻矩阵可以相乘，算法时间 O(n³)。

树形 DP

正文、推演与完整示例：树形 DP。

对每个树节点分别计算“选当前节点”和“不选当前节点”两种状态。选中时孩子都不能选；不选时每个孩子可独立取较优状态。后序递归保证孩子先算好，最后取根的两种状态较大值。 示例求最大独立集权重。

示例假设输入是一棵树。

把已访问集合编码成状态

状态压缩 DP

正文、推演与完整示例：状态压缩 DP。

mask 的每一位表示某个城市是否已经访问，dp[mask][v] 表示访问该集合并停在 v 的最短长度。对每个未访问城市尝试转移，最后加上回到起点的费用。 示例求小规模旅行商最短回路，时间 O(n²2ⁿ)。

状态数为 2ⁿ，适合 n 较小的精确求解，不适合大规模路线规划。

静态自检

把 0/1 背包改成容量正序，单件重量 2、价值 3、容量 4 会得到多少？提示：看 dp[2] 是本轮还是上轮。

参考解法

会得到 6，而正确的限用一次结果为 3；本轮更新的 dp[2] 被再次使用，相当于允许重复选择。完全背包才使用这种正序转移。