科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇以 codeforces-go 仓库 leetcode/biweekly/149/d/README.md 题解为核心完整讲解 LeetCode 双周赛 149 D 题「Minimum Cost Good Caption」从记忆化搜索到递推、再到划分型 DP 的四种解法。文中给出的所有最终版代码在仓库 d.go 中均有对应实现minCostGoodCaption1、minCostGoodCaption2、minCostGoodCaption3、minCostGoodCaption并附带可直接运行的样例与随机对拍测试。读完本文你将掌握最小操作次数 字典序最小答案这类双重优化目标的 DP 建模技巧以及「中位数贪心 划分型 DP」这一替代思路。题目与符号约定本文把输入字符串caption简记为s所有讨论均基于小写字母字符集合大小 $|\Sigma|26$。当s的长度小于 3 时无法凑出任何长度为 3 的连续相同段直接返回空字符串题面要求的无解标记下文默认n len(s) ≥ 3。一、寻找子问题从原问题到更小的子问题原问题是把s的每个连续相同段的长度都变成 ≥ 3 的最少操作次数一次操作可以把任意一个字符改成任意小写字母。同时题目还要求在操作次数最少的前提下答案字符串的字典序最小。为了让答案字典序最小我们必须从左到右思考先确定s[0]变成哪个字母再确定s[1]、s[2]……枚举s[0]变成某个字母比如a分两种情况如果s[1]也变成a那么问题变成在s[1] a的前提下s[1]到s[n-1]的最少操作次数什么时候可以让s[0]后面的位置另起炉灶如果s[1]和s[2]也变成a就能保证s[0]一定处于一个长度至少为 3 的连续相同段中此时s[3]可以换成其他字母k问题变成在s[3] k的前提下s[3]到s[n-1]的最少操作次数。这两种情况都是和原问题相似、规模更小的子问题天然适合用递归即动态规划中的自顶向下形式解决。二、状态定义与状态转移方程根据上面的讨论递归过程中需要跟踪两条信息i剩余子串从s[i]到s[n-1]j规定s[i]变成字母j下文中字母一律用 0~25 的整数表示。于是定义状态 $dfs(i,j)$在s[i] j的前提下s[i]到s[n-1]的最少操作次数。对它分类讨论情况一s[i1]也变成j代价是 $|s[i]-j|$剩余问题为 $dfs(i1,j)$情况二s[i1]和s[i2]都变成j代价是 $|s[i]-j||s[i1]-j||s[i2]-j|$且s[i3]换成字母k剩余问题为 $dfs(i3,k)$。注意这要求s[i3]到s[n-1]的长度至少是 3即 $n-(i3)\ge 3$也就是 $i\le n-6$。两种情况取最小值即得到状态转移方程$$ dfs(i,j) \min\left(dfs(i1,j) |s[i]-j|,\ \min_{k0}^{25} dfs(i3,k) |s[i]-j| |s[i1]-j| |s[i2]-j| \right) $$值得说明的是情况二无需判断 $k\ne j$。即使s[i3]恰好也变成j这也不会得到比情况一 $dfs(i1,j)$ 更优的答案——因为此时把s[i]、s[i1]、s[i2]整体并入s[i3]所在段与从s[i1]起逐位并入的效果等价且不会更差直接交给情况一即可。递归边界$dfs(n,j)0$空串代价为 0。递归入口$dfs(0,j)$最终答案取 $\min_{j0}^{25} dfs(0,j)$。三、递归搜索 保存递归返回值 记忆化搜索整个递归过程中存在大量入参相同的重复调用由于递归函数没有副作用同样的入参无论计算多少次结果都一样因此可以用记忆化搜索优化一个状态递归入参第一次遇到时在返回前把状态与结果记入memo数组再次遇到相同状态时memo中保存的结果不等于初始值直接返回缓存结果。这里有一个经典陷阱memo数组的初始值一定不能等于要记忆化的值。例如初始值设为 0而某个 $dfs(i,j)$ 恰好也等于 0就无法区分第一次遇到与之前算过导致记忆化失效。一般把初始值设为 $-1$仓库 Go 实现 d.go 正是以-1初始化memo的。Python 用户可以无视这条约定直接用cache装饰器。只计算最小操作次数的记忆化搜索代码如下输出具体方案放到下文递推中实现# 只计算最小操作次数的代码 class Solution: def minCostGoodCaption(self, s: str) - int: n len(s) if n 3: return -1 s [ord(c) - ord(a) for c in s] cache def dfs(i: int, j: int) - int: if i n: return 0 res dfs(i 1, j) abs(s[i] - j) if i n - 6: mn min(dfs(i 3, k) for k in range(26)) res min(res, mn abs(s[i] - j) abs(s[i 1] - j) abs(s[i 2] - j)) return res return min(dfs(0, j) for j in range(26))复杂度分析时间复杂度$O(n|\Sigma|^2)$其中 $n$ 是s的长度$|\Sigma|26$ 是字符集合大小。DP 时间复杂度 状态个数 × 单个状态的计算时间状态个数为 $O(n|\Sigma|)$单个状态要枚举 26 个k故总复杂度 $O(n|\Sigma|^2)$空间复杂度$O(n|\Sigma|)$保存多少状态就需要多少空间。四、1:1 翻译成递推去掉递归中的递只保留归即自底向上计算。$f[i][j]$ 的定义与 $dfs(i,j)$ 完全一致在s[i] j的前提下s[i]到s[n-1]的最少操作次数。递推式同样逐项对应$$ f[i][j] \min\left(f[i1][j] |s[i]-j|,\ \min_{k0}^{25} f[i3][k] |s[i]-j| |s[i1]-j| |s[i2]-j| \right) $$初始值 $f[n][j]0$翻译自递归边界。先给出不加任何优化的 1:1 翻译版本# 只计算最小操作次数的代码 class Solution: def minCostGoodCaption(self, s: str) - int: n len(s) if n 3: return -1 s [ord(c) - ord(a) for c in s] f [[0] * 26 for _ in range(n 1)] for i in range(n - 1, -1, -1): for j in range(26): res f[i 1][j] abs(s[i] - j) res2 min(f[i 3]) abs(s[i] - j) abs(s[i 1] - j) abs(s[i 2] - j) if i n - 6 else inf f[i][j] min(res, res2) return min(f[0])五、时间优化 输出具体方案先做时间优化把 $\min_{k0}^{25} f[i][k]$ 预存到minF[i]转移方程改写为$$ f[i][j] \min\left(f[i1][j] |s[i]-j|,\ minF[i3] |s[i]-j| |s[i1]-j| |s[i2]-j| \right) $$内层对 26 个k的枚举被 $O(1)$ 查表替代时间复杂度降为 $O(n|\Sigma|)$# 只计算最小操作次数的代码 class Solution: def minCostGoodCaption(self, s: str) - int: n len(s) if n 3: return -1 s [ord(c) - ord(a) for c in s] f [[0] * 26 for _ in range(n 1)] min_f [0] * n for i in range(n - 1, -1, -1): for j in range(26): res f[i 1][j] abs(s[i] - j) res2 min_f[i 3] abs(s[i] - j) abs(s[i 1] - j) abs(s[i 2] - j) if i n - 6 else inf f[i][j] min(res, res2) min_f[i] min(f[i]) return min_f[0]本题最终还要输出具体方案因此需要记录每个状态的最优决策来源用nxt数组记录每个状态 $f[i][j]$ 的最优决策来自哪里转移来源用minJ数组记录 $minF[i]$ 对应的是哪个j。于是当res res2时需要比较minJ[i3]与j的大小关系如果minJ[i3]更小就应选择从res2转移保证字典序最小。答疑为什么要倒着递推因为题目要构造最小字典序答案比较规则是如果两个字符串下标i处的字母相同就要根据后面的信息判断谁大谁小。只有倒着递推才能在填f[i][j]时已经获得f[i1][j]、f[i3][k]这些后面的信息。最终代码四语言完整版见原文档此处给出与仓库 d.go 中minCostGoodCaption2完全一致的 Go 版本func minCostGoodCaption(s string) string { n : len(s) if n 3 { return } f : make([][26]int, n1) minJ : make([]int, n1) nxt : make([][26]int, n1) for i : n - 1; i 0; i-- { mn : math.MaxInt for j : 0; j 26; j { res : f[i1][j] abs(int(s[i]-a)-j) res2 : math.MaxInt if i n-6 { res2 f[i3][minJ[i3]] abs(int(s[i]-a)-j) abs(int(s[i1]-a)-j) abs(int(s[i2]-a)-j) } if res2 res || res2 res minJ[i3] j { res res2 nxt[i][j] minJ[i3] // 记录转移来源 } else { nxt[i][j] j // 记录转移来源 } f[i][j] res if res mn { mn res minJ[i] j // 记录最小的 f[i][j] 中的 j 是多少 } } } ans : make([]byte, n) i, j : 0, minJ[0] for i n { ans[i] a byte(j) k : nxt[i][j] if k j { i } else { ans[i1] ans[i] ans[i2] ans[i] i 3 j k } } return string(ans) } func abs(x int) int { if x 0 { return -x }; return x }构造答案的循环逻辑从i 0, j minJ[0]出发若nxt[i][j] j说明当前位置只推进一格当前字符与下一字符同属一个正在生长的连续段否则说明s[i]、s[i1]、s[i2]三个位置统一变成j后段从i3处切换为字母k于是把三个位置一起填上j并让i 3, j k。复杂度分析时间复杂度$O(n|\Sigma|)$$n$ 是s的长度$|\Sigma|26$空间复杂度$O(n|\Sigma|)$。六、另一种思路中位数贪心 划分型 DP上述 $f[i][j]$ 的状态设计依赖字母是否相同换个角度看问题会得到更简洁的模型。注意到对于长度 ≥ 6 的子串长 6 的子串可以拆成两个长 3 的子串二者互相独立可分别计算最小修改次数长 7 的子串可以拆成长 3 和长 4 的子串分别计算长 8 的子串可以拆成长 3 长 5或长 4 长 4……因此本题的基本元素只有长为 3、4、5 的子串问题等价于把s划分成若干长为 3、4、5 的子串把每个子串中的字母都变成相同的求最小操作次数。这正是经典的划分型 DP。定义 $f[i]$ 表示后缀s[i]到s[n-1]的最小操作次数枚举第一个子串的长度 3、4、5长 3 的子串设字母排序后为 $a\le b\le c$根据中位数贪心把所有数变成中位数最优都变成 $b$ 的操作次数为 $(c-b)(b-a)c-a$长 4 的子串排序后 $a\le b\le c\le d$最小操作次数为 $cd-a-b$都变成 $b$实际上变成 $b$ 到 $c$ 之间的字母操作次数都达到最小为满足字典序最小取 $b$长 5 的子串排序后 $a\le b\le c\le d\le e$最小操作次数为 $de-a-b$都变成 $c$。于是得到转移方程$$ f[i] \min(f[i3] cost_3,\ f[i4] cost_4,\ f[i5] cost_5) $$其中 $cost_j$ 对应长为 $j$ 的子串的最小操作次数。初始值 $f[n]0,\ f[n-1]f[n-2]\infty$长度不足 3 的后缀无解。只计算代价的版本# 只计算最小操作次数的代码 class Solution: def minCostGoodCaption(self, s: str) - int: n len(s) if n 3: return -1 s list(map(ord, s)) f [0] * (n 1) f[n - 1] f[n - 2] inf for i in range(n - 3, -1, -1): a, _, c sorted(s[i: i 3]) f[i] f[i 3] c - a if i 4 n: a, b, c, d sorted(s[i: i 4]) f[i] min(f[i], f[i 4] c d - a - b) if i 5 n: a, b, _, d, e sorted(s[i: i 5]) f[i] min(f[i], f[i 5] d e - a - b) return f[0]输出具体方案如何比较字典序为了输出具体方案需要额外定义 $t_i$ 表示s[i]要变成的字母并额外比较字典序大小。仍然枚举第一个子串的长度 3、4、5长 3 的子串字母排序后为 $a,b,c$算上s[i3]要变成的字母 $t_{i3}$则前 6 个字母为 $b,b,b,t_{i3},t_{i3},t_{i3}$长 4 的子串排序后 $a,b,c,d$算上 $t_{i4}$前 6 个字母为 $b,b,b,b,t_{i4},t_{i4}$长 5 的子串排序后 $a,b,c,d,e$算上 $t_{i5}$前 6 个字母为 $c,c,c,c,c,t_{i5}$。取前 6 个字母字典序最小的方案作为最终转移来源。问为什么不考虑第 7 个字母答如果前 6 个字母都一样说明可以拆成两个长 3 的子串那么可以去掉前 3 个字母f[i]的最优决策就等同于f[i3]的最优决策对f[i]而言第 7 个字母的最优值就是f[i3]的第 4 个字母的最优值这已经在f[i3]中计算好了。又因为前 3 个字母总是一样的实际只需比较第 3 到第 6 个字母的字典序即可。下面给出优化前的 Go 实现与仓库 d.go 中minCostGoodCaption3对应用五元组(代价, 本段字母, 后续字母×3)参与比较size[i]记录本段长度func minCostGoodCaption(s string) string { n : len(s) if n 3 { return } f : make([]int, n1) f[n-1], f[n-2] math.MaxInt/2, math.MaxInt/2 t : make([]byte, n1) size : make([]uint8, n) for i : n - 3; i 0; i-- { sub : []byte(s[i : i3]) slices.Sort(sub) a, b, c : sub[0], sub[1], sub[2] s3 : int(t[i3]) res : []int{f[i3] int(c-a), int(b), s3, s3, s3} size[i] 3 if i4 n { sub : []byte(s[i : i4]) slices.Sort(sub) a, b, c, d : sub[0], sub[1], sub[2], sub[3] s4 : int(t[i4]) tp : []int{f[i4] int(c-ad-b), int(b), int(b), s4, s4} if slices.Compare(tp, res) 0 { res tp size[i] 4 } } if i5 n { sub : []byte(s[i : i5]) slices.Sort(sub) a, b, c, d, e : sub[0], sub[1], sub[2], sub[3], sub[4] tp : []int{f[i5] int(d-ae-b), int(c), int(c), int(c), int(t[i5])} if slices.Compare(tp, res) 0 { res tp size[i] 5 } } f[i] res[0] t[i] byte(res[1]) } ans : make([]byte, 0, n) for i : 0; i n; i int(size[i]) { ans append(ans, bytes.Repeat([]byte{t[i]}, int(size[i]))...) } return string(ans) }进一步优化四字母压缩进一个 int上面每轮要比较一个 5 元组可以把第 3 到第 6 个字母压缩到一个int的 4 个字节byte中比较字典序就退化为一次整数比较。以 Go 为例与仓库 d.go 中的最终版minCostGoodCaption一致func minCostGoodCaption(s string) string { n : len(s) if n 3 { return } f : make([]int, n1) f[n-1], f[n-2] math.MaxInt/2, math.MaxInt/2 t : make([]byte, n1) size : make([]uint8, n) for i : n - 3; i 0; i-- { sub : []byte(s[i : i3]) slices.Sort(sub) a, b, c : sub[0], sub[1], sub[2] s3 : int(t[i3]) res : f[i3] int(c-a) mask : int(b)24 | s316 | s38 | s3 // 4 个 byte 压缩成一个 int方便比较字典序 size[i] 3 if i4 n { sub : []byte(s[i : i4]) slices.Sort(sub) a, b, c, d : sub[0], sub[1], sub[2], sub[3] s4 : int(t[i4]) res4 : f[i4] int(c-ad-b) mask4 : int(b)24 | int(b)16 | s48 | s4 if res4 res || res4 res mask4 mask { res, mask res4, mask4 size[i] 4 } } if i5 n { sub : []byte(s[i : i5]) slices.Sort(sub) a, b, c, d, e : sub[0], sub[1], sub[2], sub[3], sub[4] res5 : f[i5] int(d-ae-b) mask5 : int(c)24 | int(c)16 | int(c)8 | int(t[i5]) if res5 res || res5 res mask5 mask { res, mask res5, mask5 size[i] 5 } } f[i] res t[i] byte(mask 24) } ans : make([]byte, 0, n) for i : 0; i n; i int(size[i]) { ans append(ans, bytes.Repeat([]byte{t[i]}, int(size[i]))...) } return string(ans) }mask的高 24 位 24恰好是本段要变成的字母b或c同时承担了t[i]的记录职责。注意对 Python 而言这可能是负优化原文档原注该技巧主要面向 C/Java/Go 这类对整型位运算友好的语言Java 版还需要把s转成 ISO-8859-1 编码的byte[]才能进行无符号的字节排序与移位。复杂度分析时间复杂度$O(n)$其中 $n$ 是s的长度。这个算法也可以理解成 $O(nk^2)$ 或 $O(nk^2\log k)$ 的算法其中 $k3$每轮对长为 3/4/5 的子串排序并比较 3 个候选空间复杂度$O(n)$。七、仓库中的实现与验证四种解法 样例 随机对拍原文档的五段核心代码与仓库 Go 实现一一对应全部集中在 d.go解法思路仓库对应函数复杂度记忆化搜索$dfs(i,j)$ memominCostGoodCaption1d.gomemo 以 -1 初始化$O(n·26^2)$ 时间 / $O(n·26)$ 空间状态机递推$f[i][j]$ 自底向上nxt/minJ记录决策minCostGoodCaption2d.go$O(n·26)$ / $O(n·26)$划分 DP元组比较中位数贪心 5 元组字典序比较minCostGoodCaption3d.go$O(n)$ / $O(n)$划分 DPint 压缩4 字母压入一个 int 比较minCostGoodCaptiond.go$O(n)$ / $O(n)$其中minCostGoodCaption1还给出了记忆化搜索的另一种等价写法不限定s[i]的字母j而是枚举k当k j时走dfs(i1,k)否则走dfs(i3,k)保证每次跳变都至少凑满长度为 3 的段并用from数组记录每个状态选择的k用于回溯构造答案。样例文件 d.txt 中保存了两组输入输出对cdcd→cccc把后两个字符改成c1 次操作即可让两个长度为 2 的段合并为长度 4 的c段aca→aaa把c改成a得到长度 3 的段bc→长度小于 3无解。测试文件 d_test.go 展示了仓库的验证方式Test_d调用 testutil.RunLeetCodeFuncWithFile从 d.txt 逐组读取输入并断言输出TestCompareInf调用 testutil.CompareInf 进行无尽随机对拍用生成器产生长度 6~15、字符范围a~f的随机串把minCostGoodCaption2状态机递推版作为参照实现与最终版minCostGoodCaption逐组对比确保两种思路在随机数据上结果完全一致。这种暴力/已证明解法对拍优化解法的测试模式在仓库的_test.go文件中被广泛使用。运行验证需在仓库根目录执行cd /data/web/disk1/git_repo/GitHub_Trending/co/codeforces-go/leetcode/biweekly/149/d go test -v八、思路总结第一套思路$f[i][j]$ 状态机从相邻字母是否相同切入天然支持从左到右构造字典序最小答案代价是状态维度为 $n×26$并需要nxt/minJ两个辅助数组记录决策第二套思路中位数贪心 划分 DP利用任何长度 ≥ 6 的段都可拆分为 3/4/5 的基本段这一结构性质把问题降维为 $O(n)$ 的划分 DP字典序比较则借助前 6 个字母的局部性完成两套思路的最终版代码都在仓库中通过样例测试与随机对拍验证可作为参赛时快速复用的模板。原文档末尾还给出了本题所属的进阶阅读路径本题在动态规划题单中属于「状态机 DP」「最优划分」「多维 DP」与「专题输出具体方案」等章节的交叉考点适合作为最小操作次数 最小字典序双目标问题的训练素材。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digitscodeforces go 仓库实战解析用栈一行思路解 LeetCode 双周赛 132 第 1 题 Clear Digits 本篇文章以 codeforce科学计算从 polar-sh/sdk1.0.0 平滑迁移到 Polar TypeScript 版本化 SDK 完整指南从 polar sh/sdk1.0.0 平滑迁移到 Polar TypeScript 版本化 SDK 完整指南 本指南面向依赖旧版 polar sh/sd科学计算codeforces-go 题解账户余额四舍五入购票LeetCode 双周赛 110 A 题——从公式推导到仓库级自动化验证codeforces go 题解账户余额四舍五入购票LeetCode 双周赛 110 A 题——从公式推导到仓库级自动化验证 本篇文章基于算法竞赛模板库科学计算上一篇Newton Viewer API 详解newton.viewer 模块的渲染后端、通用接口与图层叠加实战下一篇深入理解fhirclient架构核心组件与设计原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考