 空间优化)
LeetCode-Book 实战解析LCR 165「解密数字」的动态规划解法与 O(1) 空间优化【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读LCR 165「解密数字」是一道典型的一维线性动态规划入门题它要求统计一个数字密文ciphertext所有可行的“解码”方案数核心难点在于确定“两位数字能否被整体翻译”的判断规则并推导出状态转移方程。本文以 LeetCode-Book 仓库中 LCR 165. 解密数字 的官方题解为主体结合仓库内《剑指 Offer》同源实现函数名translateNum的 Python、Java、C 源码从“状态定义 → 转移方程 → 初始状态 → 返回值”四步完整推导并给出“字符串遍历”与“数字求余”两种实现及从 $O(N)$ 到 $O(1)$ 的空间优化过程。读完本文你将掌握一类“相邻两位可合并计数”的线性 DP 通用套路并能够把该框架迁移到 LCR 126. 斐波那契数 等同类题目上。题目背景与问题建模LCR 165 是 LeetCode《图解算法数据结构》专栏中的题目与《剑指 Offer 46. 把数字翻译成字符串》为同一问题的两个版本前者将输入命名为密文ciphertext、入口函数为crackNumber后者命名为num、入口函数为translateNum参见 剑指 Offer 46. 把数字翻译成字符串。解题内核完全一致。题目本质给定一个非负整数其中每一位数字都对应一个字符。一个数字可以被单独翻译也可以与其前一位数字组成一个两位数当且仅当该两位数在 $[10, 25]$ 区间内被整体翻译。问总共有多少种不同的翻译方案。以示例ciphertext 12258为例其可行的翻译方案共有 5 种仓库内所有sfo_46源码文件都以该数字作为测试用例运行结果均为5见各文件的Test Case与Driver Code部分。动态规划解析记数字 $ciphertext$ 第 $i$ 位数字为 $x_i$数字的位数为 $n$。例如ciphertext 12258时 $n 5$$x_1 1$。状态定义设动态规划列表 $dp$$dp[i]$ 代表以 $x_i$ 为结尾的数字的翻译方案数量。这里“以 $x_i$ 为结尾”是指只考虑密文的前 $i$ 位构成的子串能产生的翻译方案数从而把原问题拆解为规模更小、彼此独立的子问题。转移方程若 $x_i$ 与 $x_{i-1}$ 组成的两位数10 * x_{i-1} x_i可以被整体翻译则第 $i$ 位既可以“单独翻译”方案数继承 $dp[i-1]$也可以“与前一位合并翻译”方案数继承 $dp[i-2]$因此$$ dp[i] \begin{cases} dp[i - 1] dp[i - 2] {, (10 x_{i-1} x_i) \in [10,25]} \ dp[i - 1] {, (10 x_{i-1} x_i) \in [0, 10) \cup (25, 99]} \end{cases} $$可被整体翻译的两位数区间分析当 $x_{i-1} 0$ 时组成的两位数如 $00, 01, 02, \cdots$以 0 开头无法对应一个合法字符不能整体翻译大于 25 的两位数如 $26, 27, \cdots$同样超出字符映射范围也不能整体翻译。因此可合并翻译的区间恰好是 $[10, 25]$。初始状态$dp[0] dp[1] 1$即“无数字”和“第 1 位数字”的翻译方法数量均为 1。Q无数字情况 $dp[0] 1$ 从何而来A当 $ciphertext$ 第 1、2 位组成的数字 $\in [10,25]$ 时显然应有 2 种翻译方法即 $dp[2] dp[1] dp[0] 2$而显然 $dp[1] 1$因此可反推出 $dp[0] 1$。返回值返回 $dp[n]$即整个数字的翻译方案总数。这里的四步——状态定义、初始状态、转移方程、返回值——与仓库 动态规划解题框架 中总结的通用套路完全一致先定义问题最优解模型再确定基础子问题的已知解进而写出状态之间的关系最后明确迭代终止时返回哪个解。方法一字符串遍历O(N) 时间可优化至 O(1) 空间实现思路为方便获取数字的各位 $x_i$先将数字ciphertext转化为字符串s通过遍历s实现动态规划通过字符串切片s[i - 2:i]获取数字组合10 * x_{i-1} x_i并利用字符串按 ASCII 码比较的特性直接判断切片是否落在10到25之间空间使用优化由于 $dp[i]$ 只与 $dp[i - 1]$ 和 $dp[i - 2]$ 有关可用两个变量 $a, b$ 分别记录 $dp[i]$、$dp[i-1]$两变量交替前进从而省去 $dp$ 列表 $O(N)$ 的额外空间。正向遍历代码从左向右class Solution: def crackNumber(self, ciphertext: int) - int: s str(ciphertext) a b 1 for i in range(2, len(s) 1): tmp s[i - 2:i] c a b if 10 tmp 25 else a b a a c return aclass Solution { public int crackNumber(int ciphertext) { String s String.valueOf(ciphertext); int a 1, b 1; for(int i 2; i s.length(); i) { String tmp s.substring(i - 2, i); int c tmp.compareTo(10) 0 tmp.compareTo(25) 0 ? a b : a; b a; a c; } return a; } }class Solution { public: int crackNumber(int ciphertext) { string s to_string(ciphertext); int a 1, b 1, len s.size(); for(int i 2; i len; i) { string tmp s.substr(i - 2, 2); int c tmp.compare(10) 0 tmp.compare(25) 0 ? a b : a; b a; a c; } return a; } };仓库中的同名实现函数名为translateNum与上述逻辑逐行对应例如 Python 版 利用 Python 元组赋值将a, b的更新压缩为一行C 版 则用s.substr(i - 2, 2)与tmp.compare(10) 0 tmp.compare(25) 0完成切片和区间判断Java 版 使用s.substring(i - 2, i)与String.compareTo。三种语言的判断逻辑等价均可直接运行验证对12258输出5。对称性从左向右与从右向左等价此题动态规划计算是对称的即从左向右遍历从 $dp[2]$ 计算至 $dp[n]$和从右向左遍历从 $dp[n-2]$ 计算至 $dp[0]$所得方案数一致。原因是“两位数字能否合并翻译”只取决于相邻两位的取值与扫描方向无关。从右向左遍历的代码如下class Solution: def crackNumber(self, ciphertext: int) - int: s str(ciphertext) a b 1 for i in range(len(s) - 2, -1, -1): a, b (a b if 10 s[i:i 2] 25 else a), a return aclass Solution { public int crackNumber(int ciphertext) { String s String.valueOf(ciphertext); int a 1, b 1; for(int i s.length() - 2; i -1; i--) { String tmp s.substring(i, i 2); int c tmp.compareTo(10) 0 tmp.compareTo(25) 0 ? a b : a; b a; a c; } return a; } }class Solution { public: int crackNumber(int ciphertext) { string s to_string(ciphertext); int a 1, b 1, len s.size(); for(int i len - 2; i -1; i--) { string tmp s.substr(i, 2); int c tmp.compare(10) 0 tmp.compare(25) 0 ? a b : a; b a; a c; } return a; } };仓库中的 反向遍历 Python 实现 与该版本完全一致同样以12258作为测试用例。这条“对称性”结论是下一节数字求余方法能够成立的前提。方法二数字求余空间复杂度降至 O(1)空间优化原理方法一虽然已省去 $dp$ 列表的空间但字符串s仍占用 $O(N)$ 额外空间。利用求余运算ciphertext % 10和求整运算ciphertext // 10可以从个位、十位、百位……逐位取出数字从而完全摆脱字符串每次循环用ciphertext // 10去掉当前个位再用ciphertext % 10取出下一位 $x$维护变量y保存“已取出的、更低位的那一位”即相对意义上的 $x_{i-1}$用tmp 10 * x y还原相邻两位组成的数字由于处理顺序是从低位到高位天然对应从右向左的动态规划而依据上述对称性从右向左计算结果是正确的自此字符串s的空间占用被完全省去空间复杂度从 $O(N)$ 降至 $O(1)$。代码实现class Solution: def crackNumber(self, ciphertext: int) - int: a b 1 y ciphertext % 10 while ciphertext 9: ciphertext // 10 x ciphertext % 10 tmp 10 * x y c a b if 10 tmp 25 else a a, b c, a y x return aclass Solution { public int crackNumber(int ciphertext) { int a 1, b 1, x, y ciphertext % 10; while(ciphertext 9) { ciphertext / 10; x ciphertext % 10; int tmp 10 * x y; int c (tmp 10 tmp 25) ? a b : a; b a; a c; y x; } return a; } }class Solution { public: int crackNumber(int ciphertext) { int a 1, b 1, x, y ciphertext % 10; while(ciphertext 9) { ciphertext / 10; x ciphertext % 10; int tmp 10 * x y; int c (tmp 10 tmp 25) ? a b : a; b a; a c; y x; } return a; } };仓库中的 数字求余 Python 实现 与此等价且利用 Python 的元组赋值将a, b更新压缩为a, b (a b if 10 10 * x y 25 else a), a代码更为紧凑。循环条件ciphertext 9保证至少能取出两位数字参与合并判断当密文为一位数时循环不执行直接返回初始值 1即一位数字只有一种翻译方式边界处理正确。复杂度分析总结两种方法的复杂度对比如下方法时间复杂度空间复杂度额外说明方法一字符串遍历$O(N)$$O(N)$字符串s可用双变量滚动优化 $dp$ 列表方法二数字求余$O(N)$$O(1)$依赖 DP 对称性从右向左计算其中 $N$ 为字符串s的长度即数字ciphertext的位数 $\log(ciphertext)$它决定了循环次数。方法一的时间复杂度为 $O(N)$s的长度决定循环次数空间复杂度为 $O(N)$字符串s使用 $O(N)$ 额外空间方法二的时间复杂度仍为 $O(N)$但空间复杂度降为 $O(1)$仅使用几个常数大小的变量。从仓库 时间复杂度 与 空间复杂度 两篇基础文档的视角看本题是理解“以时间换空间、再以运算技巧换空间”的极佳样例先用滚动变量把 $O(N)$ 的dp数组压缩为 $O(1)$再用取余取整运算把 $O(N)$ 的字符串也消除最终达到 $O(1)$ 空间。仓库源码印证与运行验证LeetCode-Book 仓库在 sword_for_offer/codes/python 目录下提供了该题sfo_46_translate_numbers_into_strings的多版本实现包括字符串正向遍历s1、字符串反向遍历s3、数字求余s4等统一以num 12258为测试用例预期输出5num 12258 slt Solution() res slt.translateNum(num) print(res) # 5Java 与 C 版本则分别在各自目录的main()函数中完成同样的调用与输出。从源码结构可以推断这些文件遵循“Solution Code Test Case Driver Code”的统一组织方式便于读者在本地直接编译运行、验证算法正确性。此外剑指 Offer 46. 把数字翻译成字符串 题解文档还额外提供了 Python 的两种写法带临时变量tmp/c与不带可供对照学习。延伸与动态规划框架及同类题目的关联LCR 165 是仓库《图解算法数据结构》专栏“动态规划”章节的代表性例题。结合 动态规划解题框架 中总结的四步法——状态定义、初始状态、转移方程、返回值——本题可以看成斐波那契数列的推广当两位数字可合并翻译时转移方程退化为 $dp[i] dp[i-1] dp[i-2]$即斐波那契递推不可合并时则保持 $dp[i] dp[i-1]$。因此掌握本题后可以顺势迁移到该框架下列举的其他例题如 LCR 126. 斐波那契数线性递推 滚动变量、LCR 127. 跳跃训练等价于斐波那契、LCR 161. 连续天数的最高销售额一维 DP 求最大值等形成系统的动态规划解题能力。小结LCR 165「解密数字」以一道“计数型”线性 DP 题完整串联了动态规划的四个核心要素状态定义dp[i]表示前i位方案数、转移方程依据 $[10,25]$ 区间决定是否叠加 $dp[i-2]$、初始状态dp[0] dp[1] 1与返回值dp[n]。通过“字符串遍历”与“数字求余”两种实现本文展示了如何利用滚动变量与 DP 对称性将空间复杂度从 $O(N)$ 逐步压缩至 $O(1)$并给出了仓库内可复现的 Python / Java / C 多版本源码作为佐证。读者可将其作为一维线性 DP 的模板题反复练习并对照仓库题解文档体系继续深入。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 实战解析：LCR 165「解密数字」的动态规划解法与 O(1) 空间优化
LeetCode-Book 实战解析LCR 165「解密数字」的动态规划解法与 O(1) 空间优化【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读LCR 165「解密数字」是一道典型的一维线性动态规划入门题它要求统计一个数字密文ciphertext所有可行的“解码”方案数核心难点在于确定“两位数字能否被整体翻译”的判断规则并推导出状态转移方程。本文以 LeetCode-Book 仓库中 LCR 165. 解密数字 的官方题解为主体结合仓库内《剑指 Offer》同源实现函数名translateNum的 Python、Java、C 源码从“状态定义 → 转移方程 → 初始状态 → 返回值”四步完整推导并给出“字符串遍历”与“数字求余”两种实现及从 $O(N)$ 到 $O(1)$ 的空间优化过程。读完本文你将掌握一类“相邻两位可合并计数”的线性 DP 通用套路并能够把该框架迁移到 LCR 126. 斐波那契数 等同类题目上。题目背景与问题建模LCR 165 是 LeetCode《图解算法数据结构》专栏中的题目与《剑指 Offer 46. 把数字翻译成字符串》为同一问题的两个版本前者将输入命名为密文ciphertext、入口函数为crackNumber后者命名为num、入口函数为translateNum参见 剑指 Offer 46. 把数字翻译成字符串。解题内核完全一致。题目本质给定一个非负整数其中每一位数字都对应一个字符。一个数字可以被单独翻译也可以与其前一位数字组成一个两位数当且仅当该两位数在 $[10, 25]$ 区间内被整体翻译。问总共有多少种不同的翻译方案。以示例ciphertext 12258为例其可行的翻译方案共有 5 种仓库内所有sfo_46源码文件都以该数字作为测试用例运行结果均为5见各文件的Test Case与Driver Code部分。动态规划解析记数字 $ciphertext$ 第 $i$ 位数字为 $x_i$数字的位数为 $n$。例如ciphertext 12258时 $n 5$$x_1 1$。状态定义设动态规划列表 $dp$$dp[i]$ 代表以 $x_i$ 为结尾的数字的翻译方案数量。这里“以 $x_i$ 为结尾”是指只考虑密文的前 $i$ 位构成的子串能产生的翻译方案数从而把原问题拆解为规模更小、彼此独立的子问题。转移方程若 $x_i$ 与 $x_{i-1}$ 组成的两位数10 * x_{i-1} x_i可以被整体翻译则第 $i$ 位既可以“单独翻译”方案数继承 $dp[i-1]$也可以“与前一位合并翻译”方案数继承 $dp[i-2]$因此$$ dp[i] \begin{cases} dp[i - 1] dp[i - 2] {, (10 x_{i-1} x_i) \in [10,25]} \ dp[i - 1] {, (10 x_{i-1} x_i) \in [0, 10) \cup (25, 99]} \end{cases} $$可被整体翻译的两位数区间分析当 $x_{i-1} 0$ 时组成的两位数如 $00, 01, 02, \cdots$以 0 开头无法对应一个合法字符不能整体翻译大于 25 的两位数如 $26, 27, \cdots$同样超出字符映射范围也不能整体翻译。因此可合并翻译的区间恰好是 $[10, 25]$。初始状态$dp[0] dp[1] 1$即“无数字”和“第 1 位数字”的翻译方法数量均为 1。Q无数字情况 $dp[0] 1$ 从何而来A当 $ciphertext$ 第 1、2 位组成的数字 $\in [10,25]$ 时显然应有 2 种翻译方法即 $dp[2] dp[1] dp[0] 2$而显然 $dp[1] 1$因此可反推出 $dp[0] 1$。返回值返回 $dp[n]$即整个数字的翻译方案总数。这里的四步——状态定义、初始状态、转移方程、返回值——与仓库 动态规划解题框架 中总结的通用套路完全一致先定义问题最优解模型再确定基础子问题的已知解进而写出状态之间的关系最后明确迭代终止时返回哪个解。方法一字符串遍历O(N) 时间可优化至 O(1) 空间实现思路为方便获取数字的各位 $x_i$先将数字ciphertext转化为字符串s通过遍历s实现动态规划通过字符串切片s[i - 2:i]获取数字组合10 * x_{i-1} x_i并利用字符串按 ASCII 码比较的特性直接判断切片是否落在10到25之间空间使用优化由于 $dp[i]$ 只与 $dp[i - 1]$ 和 $dp[i - 2]$ 有关可用两个变量 $a, b$ 分别记录 $dp[i]$、$dp[i-1]$两变量交替前进从而省去 $dp$ 列表 $O(N)$ 的额外空间。正向遍历代码从左向右class Solution: def crackNumber(self, ciphertext: int) - int: s str(ciphertext) a b 1 for i in range(2, len(s) 1): tmp s[i - 2:i] c a b if 10 tmp 25 else a b a a c return aclass Solution { public int crackNumber(int ciphertext) { String s String.valueOf(ciphertext); int a 1, b 1; for(int i 2; i s.length(); i) { String tmp s.substring(i - 2, i); int c tmp.compareTo(10) 0 tmp.compareTo(25) 0 ? a b : a; b a; a c; } return a; } }class Solution { public: int crackNumber(int ciphertext) { string s to_string(ciphertext); int a 1, b 1, len s.size(); for(int i 2; i len; i) { string tmp s.substr(i - 2, 2); int c tmp.compare(10) 0 tmp.compare(25) 0 ? a b : a; b a; a c; } return a; } };仓库中的同名实现函数名为translateNum与上述逻辑逐行对应例如 Python 版 利用 Python 元组赋值将a, b的更新压缩为一行C 版 则用s.substr(i - 2, 2)与tmp.compare(10) 0 tmp.compare(25) 0完成切片和区间判断Java 版 使用s.substring(i - 2, i)与String.compareTo。三种语言的判断逻辑等价均可直接运行验证对12258输出5。对称性从左向右与从右向左等价此题动态规划计算是对称的即从左向右遍历从 $dp[2]$ 计算至 $dp[n]$和从右向左遍历从 $dp[n-2]$ 计算至 $dp[0]$所得方案数一致。原因是“两位数字能否合并翻译”只取决于相邻两位的取值与扫描方向无关。从右向左遍历的代码如下class Solution: def crackNumber(self, ciphertext: int) - int: s str(ciphertext) a b 1 for i in range(len(s) - 2, -1, -1): a, b (a b if 10 s[i:i 2] 25 else a), a return aclass Solution { public int crackNumber(int ciphertext) { String s String.valueOf(ciphertext); int a 1, b 1; for(int i s.length() - 2; i -1; i--) { String tmp s.substring(i, i 2); int c tmp.compareTo(10) 0 tmp.compareTo(25) 0 ? a b : a; b a; a c; } return a; } }class Solution { public: int crackNumber(int ciphertext) { string s to_string(ciphertext); int a 1, b 1, len s.size(); for(int i len - 2; i -1; i--) { string tmp s.substr(i, 2); int c tmp.compare(10) 0 tmp.compare(25) 0 ? a b : a; b a; a c; } return a; } };仓库中的 反向遍历 Python 实现 与该版本完全一致同样以12258作为测试用例。这条“对称性”结论是下一节数字求余方法能够成立的前提。方法二数字求余空间复杂度降至 O(1)空间优化原理方法一虽然已省去 $dp$ 列表的空间但字符串s仍占用 $O(N)$ 额外空间。利用求余运算ciphertext % 10和求整运算ciphertext // 10可以从个位、十位、百位……逐位取出数字从而完全摆脱字符串每次循环用ciphertext // 10去掉当前个位再用ciphertext % 10取出下一位 $x$维护变量y保存“已取出的、更低位的那一位”即相对意义上的 $x_{i-1}$用tmp 10 * x y还原相邻两位组成的数字由于处理顺序是从低位到高位天然对应从右向左的动态规划而依据上述对称性从右向左计算结果是正确的自此字符串s的空间占用被完全省去空间复杂度从 $O(N)$ 降至 $O(1)$。代码实现class Solution: def crackNumber(self, ciphertext: int) - int: a b 1 y ciphertext % 10 while ciphertext 9: ciphertext // 10 x ciphertext % 10 tmp 10 * x y c a b if 10 tmp 25 else a a, b c, a y x return aclass Solution { public int crackNumber(int ciphertext) { int a 1, b 1, x, y ciphertext % 10; while(ciphertext 9) { ciphertext / 10; x ciphertext % 10; int tmp 10 * x y; int c (tmp 10 tmp 25) ? a b : a; b a; a c; y x; } return a; } }class Solution { public: int crackNumber(int ciphertext) { int a 1, b 1, x, y ciphertext % 10; while(ciphertext 9) { ciphertext / 10; x ciphertext % 10; int tmp 10 * x y; int c (tmp 10 tmp 25) ? a b : a; b a; a c; y x; } return a; } };仓库中的 数字求余 Python 实现 与此等价且利用 Python 的元组赋值将a, b更新压缩为a, b (a b if 10 10 * x y 25 else a), a代码更为紧凑。循环条件ciphertext 9保证至少能取出两位数字参与合并判断当密文为一位数时循环不执行直接返回初始值 1即一位数字只有一种翻译方式边界处理正确。复杂度分析总结两种方法的复杂度对比如下方法时间复杂度空间复杂度额外说明方法一字符串遍历$O(N)$$O(N)$字符串s可用双变量滚动优化 $dp$ 列表方法二数字求余$O(N)$$O(1)$依赖 DP 对称性从右向左计算其中 $N$ 为字符串s的长度即数字ciphertext的位数 $\log(ciphertext)$它决定了循环次数。方法一的时间复杂度为 $O(N)$s的长度决定循环次数空间复杂度为 $O(N)$字符串s使用 $O(N)$ 额外空间方法二的时间复杂度仍为 $O(N)$但空间复杂度降为 $O(1)$仅使用几个常数大小的变量。从仓库 时间复杂度 与 空间复杂度 两篇基础文档的视角看本题是理解“以时间换空间、再以运算技巧换空间”的极佳样例先用滚动变量把 $O(N)$ 的dp数组压缩为 $O(1)$再用取余取整运算把 $O(N)$ 的字符串也消除最终达到 $O(1)$ 空间。仓库源码印证与运行验证LeetCode-Book 仓库在 sword_for_offer/codes/python 目录下提供了该题sfo_46_translate_numbers_into_strings的多版本实现包括字符串正向遍历s1、字符串反向遍历s3、数字求余s4等统一以num 12258为测试用例预期输出5num 12258 slt Solution() res slt.translateNum(num) print(res) # 5Java 与 C 版本则分别在各自目录的main()函数中完成同样的调用与输出。从源码结构可以推断这些文件遵循“Solution Code Test Case Driver Code”的统一组织方式便于读者在本地直接编译运行、验证算法正确性。此外剑指 Offer 46. 把数字翻译成字符串 题解文档还额外提供了 Python 的两种写法带临时变量tmp/c与不带可供对照学习。延伸与动态规划框架及同类题目的关联LCR 165 是仓库《图解算法数据结构》专栏“动态规划”章节的代表性例题。结合 动态规划解题框架 中总结的四步法——状态定义、初始状态、转移方程、返回值——本题可以看成斐波那契数列的推广当两位数字可合并翻译时转移方程退化为 $dp[i] dp[i-1] dp[i-2]$即斐波那契递推不可合并时则保持 $dp[i] dp[i-1]$。因此掌握本题后可以顺势迁移到该框架下列举的其他例题如 LCR 126. 斐波那契数线性递推 滚动变量、LCR 127. 跳跃训练等价于斐波那契、LCR 161. 连续天数的最高销售额一维 DP 求最大值等形成系统的动态规划解题能力。小结LCR 165「解密数字」以一道“计数型”线性 DP 题完整串联了动态规划的四个核心要素状态定义dp[i]表示前i位方案数、转移方程依据 $[10,25]$ 区间决定是否叠加 $dp[i-2]$、初始状态dp[0] dp[1] 1与返回值dp[n]。通过“字符串遍历”与“数字求余”两种实现本文展示了如何利用滚动变量与 DP 对称性将空间复杂度从 $O(N)$ 逐步压缩至 $O(1)$并给出了仓库内可复现的 Python / Java / C 多版本源码作为佐证。读者可将其作为一维线性 DP 的模板题反复练习并对照仓库题解文档体系继续深入。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考