科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以算法竞赛模板库 codeforces-go 中收录的 LeetCode 第 298 场周赛 D 题2312. 卖木头块题解 为核心骨架完整讲解「高宽二维木块的区间 DP」思路从第一步切割方案出发寻找子问题、定义状态f[i][j]、推导垂直/水平切割的转移方程并给出 Python、Java、C、Go、JavaScript、Rust 六种语言的完整实现与「枚举一半」优化。读者读完可以掌握一类二维区间划分型动态规划的通用套路并了解该题解在仓库中的 Go 实现、测试框架与用例组织方式。题目背景与仓库中的对应组织「卖木头块」Selling Pieces of Wood是 LeetCode 2312 题题目模型为给定一块高m、宽n的木块可以按任意顺序进行水平或垂直切割每切一刀得到两块更小的木块另有若干[h, w, price]的三元组表示「恰好高h、宽w的木块可以直接按price售出」目标是把整块木头切完后允许不切、允许丢弃部分实际题目中所有切出的木块都可出售或不售出能得到的最大总收益。在 codeforces-go 仓库中该题按「场次/题号」方式归档题解文档leetcode/weekly/298/d/README.mdGo 参考实现leetcode/weekly/298/d/d.go测试驱动与用例leetcode/weekly/298/d/d_test.go、leetcode/weekly/298/d/d.txt寻找子问题第一步有多少种切法先看示例 1一块高为 3、宽为 5 的木块第一步一共有 6 种切割方案竖着切开有 4 种切法宽度切成 14、23、32、41横着切开有 2 种切法高度切成 12、21。例如横着切开第一步可以分成一个高为 2、宽为 5 的木块和一个高为 1、宽为 5 的木块。关键观察这两个木块都是更小的木块可以分别独立处理、接着切割比如第一块横切、第二块竖切。这意味着我们始终要处理的问题是「高为i、宽为j的木块」原问题被自然拆解为同构的规模更小的子问题——这正是区间 DP 的典型结构。状态定义与转移方程状态定义定义f[i][j]表示切割一块高为i、宽为j的木块能得到的最多钱数。分类讨论三种取值来源对于状态f[i][j]逐一考虑所有可能的第一刀或直接出售直接售卖如果存在高i、宽j对应的价格price则收益为该价格竖着切开枚举切割位置宽度k得到两个高为i宽分别为k与j-k的木块最大收益为$$ \max_{k1}^{j-1} f[i][k]f[i][j-k] $$横着切开枚举切割位置高度k得到两个宽为j高分别为k与i-k的木块最大收益为$$ \max_{k1}^{i-1} f[k][j]f[i-k][j] $$取上述三种情况的最大值即为f[i][j]。最终答案就是f[m][n]。为什么这样枚举是完备的因为任意一块木块其第一刀要么不做直接卖要么水平切、要么垂直切切完后两块子木块的最优收益恰好是各自f的最优值最优子结构成立因此自底向上按i、j递增的顺序计算即可。价格的存储方式代码实现时为了方便查询木块价格可以用一个哈希表或二维数组记录「高宽 → 价格」的映射Python 用字典{(h, w): p}Java / C / Go / JS / Rust 用(m1) × (n1)的二维数组pr对每个prices项执行pr[h][w] p。原文档指出这种额外记录并非必要在后面的优化小节中会直接复用f数组本身来存价格。第一版实现六种语言Python3class Solution: def sellingWood(self, m: int, n: int, prices: List[List[int]]) - int: pr {(h, w): p for h, w, p in prices} f [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(pr.get((i, j), 0), max((f[i][k] f[i][j - k] for k in range(1, j)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i)), default0)) # 水平切割 return f[m][n]Javaclass Solution { public long sellingWood(int m, int n, int[][] prices) { int[][] pr new int[m 1][n 1]; for (int[] p : prices) { pr[p[0]][p[1]] p[2]; } long[][] f new long[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { f[i][j] pr[i][j]; for (int k 1; k j; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } }Cclass Solution { public: long long sellingWood(int m, int n, vectorvectorint prices) { vectorvectorint pr(m 1, vectorint(n 1)); for (auto p: prices) { pr[p[0]][p[1]] p[2]; } vectorvectorlong long f(m 1, vectorlong long(n 1)); for (int i 1; i m; i) { for (int j 1; j n; j) { f[i][j] pr[i][j]; for (int k 1; k j; k) f[i][j] max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i; k) f[i][j] max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } };Gofunc sellingWood(m, n int, prices [][]int) int64 { pr : make([][]int, m1) for i : range pr { pr[i] make([]int, n1) } for _, price : range prices { pr[price[0]][price[1]] price[2] } f : make([][]int64, m1) for i : 1; i m; i { f[i] make([]int64, n1) for j : 1; j n; j { f[i][j] int64(pr[i][j]) for k : 1; k j; k { // 垂直切割枚举宽度 k f[i][j] max(f[i][j], f[i][k]f[i][j-k]) } for k : 1; k i; k { // 水平切割枚举高度 k f[i][j] max(f[i][j], f[k][j]f[i-k][j]) } } } return f[m][n] }JavaScriptvar sellingWood function(m, n, prices) { const pr Array.from({length: m 1}, () Array(n 1).fill(0)); for (const [w, h, p] of prices) { pr[w][h] p; } const f Array.from({length: m 1}, () Array(n 1).fill(0)); for (let i 1; i m; i) { for (let j 1; j n; j) { f[i][j] pr[i][j]; for (let k 1; k j; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (let k 1; k i; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; };Rustimpl Solution { pub fn selling_wood(m: i32, n: i32, prices: VecVeci32) - i64 { let m m as usize; let n n as usize; let mut pr vec![vec![0; n 1]; m 1]; for p in prices { pr[p[0] as usize][p[1] as usize] p[2]; } let mut f vec![vec![0; n 1]; m 1]; for i in 1..m { for j in 1..n { f[i][j] pr[i][j] as i64; for k in 1..j { // 垂直切割枚举宽度 k f[i][j] f[i][j].max(f[i][k] f[i][j - k]); } for k in 1..i { // 水平切割枚举高度 k f[i][j] f[i][j].max(f[k][j] f[i - k][j]); } } } f[m][n] } }优化枚举一半即可回顾第一步的切割方案。对于高为 3、宽为 5 的木块第一步共有 6 种切法竖切 4 种、横切 2 种。但实际上横着切位置不同但得到的结果是相同的——都是「高 2 宽 5」「高 1 宽 5」本质上只有 1 种切法竖着切同理切在宽度 1 和切在宽度 4 得到的两块只是左右互换本质上是同一组分块因此本质上只有 2 种切法。结论枚举k时只需要枚举到一半位置。垂直切割时宽度至多枚举到 $\left\lfloor\dfrac{j}{2}\right\rfloor$水平切割时高度至多枚举到 $\left\lfloor\dfrac{i}{2}\right\rfloor$。这不会漏掉任何一组划分(k, j-k)与(j-k, k)是同一种划分取对称的一半即可覆盖全部。另外计算递推之前可以直接把prices记录到f数组中省去单独的pr数组减少一个二维数组的开销。优化后的核心循环变为for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(f[i][j], max((f[i][k] f[i][j - k] for k in range(1, j // 2 1)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i // 2 1)), default0)) # 水平切割Python3优化版class Solution: def sellingWood(self, m: int, n: int, prices: List[List[int]]) - int: f [[0] * (n 1) for _ in range(m 1)] for h, w, p in prices: f[h][w] p for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(f[i][j], max((f[i][k] f[i][j - k] for k in range(1, j // 2 1)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i // 2 1)), default0)) # 水平切割 return f[m][n]Java优化版class Solution { public long sellingWood(int m, int n, int[][] prices) { long[][] f new long[m 1][n 1]; for (int[] p : prices) { f[p[0]][p[1]] p[2]; } for (int i 1; i m; i) { for (int j 1; j n; j) { for (int k 1; k j / 2; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i / 2; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } }C优化版class Solution { public: long long sellingWood(int m, int n, vectorvectorint prices) { vectorvectorlong long f(m 1, vectorlong long(n 1)); for (auto p : prices) { f[p[0]][p[1]] p[2]; } for (int i 1; i m; i) { for (int j 1; j n; j) { for (int k 1; k j / 2; k) f[i][j] max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i / 2; k) f[i][j] max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } };Go优化版func sellingWood(m, n int, prices [][]int) int64 { f : make([][]int64, m1) for i : range f { f[i] make([]int64, n1) } for _, price : range prices { f[price[0]][price[1]] int64(price[2]) } for i : 1; i m; i { for j : 1; j n; j { for k : 1; k j/2; k { // 垂直切割枚举宽度 k f[i][j] max(f[i][j], f[i][k]f[i][j-k]) } for k : 1; k i/2; k { // 水平切割枚举高度 k f[i][j] max(f[i][j], f[k][j]f[i-k][j]) } } } return f[m][n] }说明原题解文档在优化小节给出的 JavaScript 与 Rust 版本仍按完整枚举k j/k i编写仅去掉了pr数组枚举范围收敛到一半这一改动对任何语言同样适用读者可自行对照替换。复杂度分析时间复杂度$\mathcal{O}(mn(mn))$。i、j两重循环遍历全部 $m \times n$ 个状态每个状态枚举约 $\frac{j}{2}$ 次宽度与 $\frac{i}{2}$ 次高度合计为 $\mathcal{O}(mn \cdot (mn))$空间复杂度$\mathcal{O}(mn)$。只使用一个(m1) × (n1)的 DP 数组f。注意题目收益可能较大Java / C / Go / Rust 中f使用 64 位整数类型long/long long/int64/i64避免溢出。仓库中的 Go 实现、测试框架与用例验证Go 参考实现leetcode/weekly/298/d/d.go 与题解文档中的优化版 Go 代码完全对应f初始化为[][]int64先读入prices写入f[h][w]再按i、j递增顺序转移垂直/水平切割均只枚举到j/2、i/2最终返回f[m][n]。可以看到代码顶部还保留了视频讲解来源的注释https://space.bilibili.com/206214/dynamic是该仓库「题目 题解文档 可运行代码」一体归档风格的体现。测试用例文件leetcode/weekly/298/d/d.txt 以「每 4 行一组」的方式存放原始用例3 行输入 1 行期望输出包括m3, n5, prices[[1,4,2],[2,2,7],[2,1,3]]→ 期望19m4, n6, prices[[3,2,10],[1,4,2],[4,1,3]]→ 期望32m9, n7, prices[[4,3,2],[5,3,16],[4,4,18],[8,7,6]]→ 期望54一组大规模数据m37, n77约 100 个价格三元组 → 期望79128416用于检验算法在较大规模下的正确性与性能。测试框架leetcode/weekly/298/d/d_test.go 通过testutil.RunLeetCodeFuncWithFile读取d.txt并自动驱动测试func Test_d(t *testing.T) { targetCaseNum : -1 if err : testutil.RunLeetCodeFuncWithFile(t, sellingWood, d.txt, targetCaseNum); err ! nil { t.Fatal(err) } }其中targetCaseNum -1表示从最后一个用例开始跑即先验证大数据用例随后跑完全部用例其语义在 leetcode/testutil/leetcode.go 的RunLeetCodeFuncWithFile/RunLeetCodeFuncWithExamples中定义负值会把targetCaseNum折算为len(rawExamples) 1 targetCaseNum为 0 时则跑全部用例。测试框架通过反射解析函数签名与d.txt中的原始数据数组、整数、int64等逐条断言输出并对全量跑用例时的超时进行检测。如何本地运行验证在仓库根目录执行以下命令即可跑通本题的 Go 解法与全部测试用例go test ./leetcode/weekly/298/d/ -run Test_d -v运行成功后输出类似case -1 is passed以及各用例OK的结果说明题解实现与官方测试数据一致。若只希望运行单个用例可将d_test.go中targetCaseNum改为正数如 1、2、3后再次运行。小结一类二维划分 DP 的通用套路从本题可以提炼出二维区间划分型 DP 的通用模式找子问题第一刀要么不切直接卖要么水平切、要么垂直切切出的两块都是更小尺寸的同构问题定状态f[i][j]表示高i宽j的木块能获得的最大收益列转移对每个方向枚举切点kf[i][j] max(直接价格, f[i][k]f[i][j-k], f[k][j]f[i-k][j])做优化切点枚举到一半即可避免对称重复价格可预写入f数组省去额外存储算复杂度$\mathcal{O}(mn(mn))$ 时间、$\mathcal{O}(mn)$ 空间。该解法在仓库中由 题解文档、Go 实现 与 测试数据 三位一体构成可直接作为后续同类划分/切割问题的参考模板。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐数位 DP 实战解析LeetCode 2719「区间内美丽整数的数目」——以 codeforces-go 仓库的四语言题解与通用模板为参照数位 DP 实战解析LeetCode 2719「区间内美丽整数的数目」——以 codeforces go 仓库的四语言题解与通用模板为参照 本篇文章以算法竞赛科学计算codeforces-go 仓库题解精读LeetCode 2490「环形句子」(Circular Sentence) 多语言实现与测试框架解析codeforces go 仓库题解精读LeetCode 2490「环形句子」 Circular Sentence 多语言实现与测试框架解析 本篇文章精讲 L科学计算codeforces-go 仓库实战LeetCode 1929「数组串联」两种写法的多语言实现与仓库源码验证codeforces go 仓库实战LeetCode 1929「数组串联」两种写法的多语言实现与仓库源码验证 本文以 leetcode/weekly/249/科学计算上一篇PARD-Qwen3-0.6B模型架构详解从Qwen3到PARD优化的完整技术栈下一篇Otto HandlerFinder机制揭秘事件处理器的发现与注册原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/10 1:47:48 · 阅读 1.2k codeforces-go 仓库实战解析：LeetCode 2312「卖木头块」区间 DP 题解与多语言实现
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以算法竞赛模板库 codeforces-go 中收录的 LeetCode 第 298 场周赛 D 题2312. 卖木头块题解 为核心骨架完整讲解「高宽二维木块的区间 DP」思路从第一步切割方案出发寻找子问题、定义状态f[i][j]、推导垂直/水平切割的转移方程并给出 Python、Java、C、Go、JavaScript、Rust 六种语言的完整实现与「枚举一半」优化。读者读完可以掌握一类二维区间划分型动态规划的通用套路并了解该题解在仓库中的 Go 实现、测试框架与用例组织方式。题目背景与仓库中的对应组织「卖木头块」Selling Pieces of Wood是 LeetCode 2312 题题目模型为给定一块高m、宽n的木块可以按任意顺序进行水平或垂直切割每切一刀得到两块更小的木块另有若干[h, w, price]的三元组表示「恰好高h、宽w的木块可以直接按price售出」目标是把整块木头切完后允许不切、允许丢弃部分实际题目中所有切出的木块都可出售或不售出能得到的最大总收益。在 codeforces-go 仓库中该题按「场次/题号」方式归档题解文档leetcode/weekly/298/d/README.mdGo 参考实现leetcode/weekly/298/d/d.go测试驱动与用例leetcode/weekly/298/d/d_test.go、leetcode/weekly/298/d/d.txt寻找子问题第一步有多少种切法先看示例 1一块高为 3、宽为 5 的木块第一步一共有 6 种切割方案竖着切开有 4 种切法宽度切成 14、23、32、41横着切开有 2 种切法高度切成 12、21。例如横着切开第一步可以分成一个高为 2、宽为 5 的木块和一个高为 1、宽为 5 的木块。关键观察这两个木块都是更小的木块可以分别独立处理、接着切割比如第一块横切、第二块竖切。这意味着我们始终要处理的问题是「高为i、宽为j的木块」原问题被自然拆解为同构的规模更小的子问题——这正是区间 DP 的典型结构。状态定义与转移方程状态定义定义f[i][j]表示切割一块高为i、宽为j的木块能得到的最多钱数。分类讨论三种取值来源对于状态f[i][j]逐一考虑所有可能的第一刀或直接出售直接售卖如果存在高i、宽j对应的价格price则收益为该价格竖着切开枚举切割位置宽度k得到两个高为i宽分别为k与j-k的木块最大收益为$$ \max_{k1}^{j-1} f[i][k]f[i][j-k] $$横着切开枚举切割位置高度k得到两个宽为j高分别为k与i-k的木块最大收益为$$ \max_{k1}^{i-1} f[k][j]f[i-k][j] $$取上述三种情况的最大值即为f[i][j]。最终答案就是f[m][n]。为什么这样枚举是完备的因为任意一块木块其第一刀要么不做直接卖要么水平切、要么垂直切切完后两块子木块的最优收益恰好是各自f的最优值最优子结构成立因此自底向上按i、j递增的顺序计算即可。价格的存储方式代码实现时为了方便查询木块价格可以用一个哈希表或二维数组记录「高宽 → 价格」的映射Python 用字典{(h, w): p}Java / C / Go / JS / Rust 用(m1) × (n1)的二维数组pr对每个prices项执行pr[h][w] p。原文档指出这种额外记录并非必要在后面的优化小节中会直接复用f数组本身来存价格。第一版实现六种语言Python3class Solution: def sellingWood(self, m: int, n: int, prices: List[List[int]]) - int: pr {(h, w): p for h, w, p in prices} f [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(pr.get((i, j), 0), max((f[i][k] f[i][j - k] for k in range(1, j)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i)), default0)) # 水平切割 return f[m][n]Javaclass Solution { public long sellingWood(int m, int n, int[][] prices) { int[][] pr new int[m 1][n 1]; for (int[] p : prices) { pr[p[0]][p[1]] p[2]; } long[][] f new long[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { f[i][j] pr[i][j]; for (int k 1; k j; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } }Cclass Solution { public: long long sellingWood(int m, int n, vectorvectorint prices) { vectorvectorint pr(m 1, vectorint(n 1)); for (auto p: prices) { pr[p[0]][p[1]] p[2]; } vectorvectorlong long f(m 1, vectorlong long(n 1)); for (int i 1; i m; i) { for (int j 1; j n; j) { f[i][j] pr[i][j]; for (int k 1; k j; k) f[i][j] max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i; k) f[i][j] max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } };Gofunc sellingWood(m, n int, prices [][]int) int64 { pr : make([][]int, m1) for i : range pr { pr[i] make([]int, n1) } for _, price : range prices { pr[price[0]][price[1]] price[2] } f : make([][]int64, m1) for i : 1; i m; i { f[i] make([]int64, n1) for j : 1; j n; j { f[i][j] int64(pr[i][j]) for k : 1; k j; k { // 垂直切割枚举宽度 k f[i][j] max(f[i][j], f[i][k]f[i][j-k]) } for k : 1; k i; k { // 水平切割枚举高度 k f[i][j] max(f[i][j], f[k][j]f[i-k][j]) } } } return f[m][n] }JavaScriptvar sellingWood function(m, n, prices) { const pr Array.from({length: m 1}, () Array(n 1).fill(0)); for (const [w, h, p] of prices) { pr[w][h] p; } const f Array.from({length: m 1}, () Array(n 1).fill(0)); for (let i 1; i m; i) { for (let j 1; j n; j) { f[i][j] pr[i][j]; for (let k 1; k j; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (let k 1; k i; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; };Rustimpl Solution { pub fn selling_wood(m: i32, n: i32, prices: VecVeci32) - i64 { let m m as usize; let n n as usize; let mut pr vec![vec![0; n 1]; m 1]; for p in prices { pr[p[0] as usize][p[1] as usize] p[2]; } let mut f vec![vec![0; n 1]; m 1]; for i in 1..m { for j in 1..n { f[i][j] pr[i][j] as i64; for k in 1..j { // 垂直切割枚举宽度 k f[i][j] f[i][j].max(f[i][k] f[i][j - k]); } for k in 1..i { // 水平切割枚举高度 k f[i][j] f[i][j].max(f[k][j] f[i - k][j]); } } } f[m][n] } }优化枚举一半即可回顾第一步的切割方案。对于高为 3、宽为 5 的木块第一步共有 6 种切法竖切 4 种、横切 2 种。但实际上横着切位置不同但得到的结果是相同的——都是「高 2 宽 5」「高 1 宽 5」本质上只有 1 种切法竖着切同理切在宽度 1 和切在宽度 4 得到的两块只是左右互换本质上是同一组分块因此本质上只有 2 种切法。结论枚举k时只需要枚举到一半位置。垂直切割时宽度至多枚举到 $\left\lfloor\dfrac{j}{2}\right\rfloor$水平切割时高度至多枚举到 $\left\lfloor\dfrac{i}{2}\right\rfloor$。这不会漏掉任何一组划分(k, j-k)与(j-k, k)是同一种划分取对称的一半即可覆盖全部。另外计算递推之前可以直接把prices记录到f数组中省去单独的pr数组减少一个二维数组的开销。优化后的核心循环变为for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(f[i][j], max((f[i][k] f[i][j - k] for k in range(1, j // 2 1)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i // 2 1)), default0)) # 水平切割Python3优化版class Solution: def sellingWood(self, m: int, n: int, prices: List[List[int]]) - int: f [[0] * (n 1) for _ in range(m 1)] for h, w, p in prices: f[h][w] p for i in range(1, m 1): for j in range(1, n 1): f[i][j] max(f[i][j], max((f[i][k] f[i][j - k] for k in range(1, j // 2 1)), default0), # 垂直切割 max((f[k][j] f[i - k][j] for k in range(1, i // 2 1)), default0)) # 水平切割 return f[m][n]Java优化版class Solution { public long sellingWood(int m, int n, int[][] prices) { long[][] f new long[m 1][n 1]; for (int[] p : prices) { f[p[0]][p[1]] p[2]; } for (int i 1; i m; i) { for (int j 1; j n; j) { for (int k 1; k j / 2; k) f[i][j] Math.max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i / 2; k) f[i][j] Math.max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } }C优化版class Solution { public: long long sellingWood(int m, int n, vectorvectorint prices) { vectorvectorlong long f(m 1, vectorlong long(n 1)); for (auto p : prices) { f[p[0]][p[1]] p[2]; } for (int i 1; i m; i) { for (int j 1; j n; j) { for (int k 1; k j / 2; k) f[i][j] max(f[i][j], f[i][k] f[i][j - k]); // 垂直切割 for (int k 1; k i / 2; k) f[i][j] max(f[i][j], f[k][j] f[i - k][j]); // 水平切割 } } return f[m][n]; } };Go优化版func sellingWood(m, n int, prices [][]int) int64 { f : make([][]int64, m1) for i : range f { f[i] make([]int64, n1) } for _, price : range prices { f[price[0]][price[1]] int64(price[2]) } for i : 1; i m; i { for j : 1; j n; j { for k : 1; k j/2; k { // 垂直切割枚举宽度 k f[i][j] max(f[i][j], f[i][k]f[i][j-k]) } for k : 1; k i/2; k { // 水平切割枚举高度 k f[i][j] max(f[i][j], f[k][j]f[i-k][j]) } } } return f[m][n] }说明原题解文档在优化小节给出的 JavaScript 与 Rust 版本仍按完整枚举k j/k i编写仅去掉了pr数组枚举范围收敛到一半这一改动对任何语言同样适用读者可自行对照替换。复杂度分析时间复杂度$\mathcal{O}(mn(mn))$。i、j两重循环遍历全部 $m \times n$ 个状态每个状态枚举约 $\frac{j}{2}$ 次宽度与 $\frac{i}{2}$ 次高度合计为 $\mathcal{O}(mn \cdot (mn))$空间复杂度$\mathcal{O}(mn)$。只使用一个(m1) × (n1)的 DP 数组f。注意题目收益可能较大Java / C / Go / Rust 中f使用 64 位整数类型long/long long/int64/i64避免溢出。仓库中的 Go 实现、测试框架与用例验证Go 参考实现leetcode/weekly/298/d/d.go 与题解文档中的优化版 Go 代码完全对应f初始化为[][]int64先读入prices写入f[h][w]再按i、j递增顺序转移垂直/水平切割均只枚举到j/2、i/2最终返回f[m][n]。可以看到代码顶部还保留了视频讲解来源的注释https://space.bilibili.com/206214/dynamic是该仓库「题目 题解文档 可运行代码」一体归档风格的体现。测试用例文件leetcode/weekly/298/d/d.txt 以「每 4 行一组」的方式存放原始用例3 行输入 1 行期望输出包括m3, n5, prices[[1,4,2],[2,2,7],[2,1,3]]→ 期望19m4, n6, prices[[3,2,10],[1,4,2],[4,1,3]]→ 期望32m9, n7, prices[[4,3,2],[5,3,16],[4,4,18],[8,7,6]]→ 期望54一组大规模数据m37, n77约 100 个价格三元组 → 期望79128416用于检验算法在较大规模下的正确性与性能。测试框架leetcode/weekly/298/d/d_test.go 通过testutil.RunLeetCodeFuncWithFile读取d.txt并自动驱动测试func Test_d(t *testing.T) { targetCaseNum : -1 if err : testutil.RunLeetCodeFuncWithFile(t, sellingWood, d.txt, targetCaseNum); err ! nil { t.Fatal(err) } }其中targetCaseNum -1表示从最后一个用例开始跑即先验证大数据用例随后跑完全部用例其语义在 leetcode/testutil/leetcode.go 的RunLeetCodeFuncWithFile/RunLeetCodeFuncWithExamples中定义负值会把targetCaseNum折算为len(rawExamples) 1 targetCaseNum为 0 时则跑全部用例。测试框架通过反射解析函数签名与d.txt中的原始数据数组、整数、int64等逐条断言输出并对全量跑用例时的超时进行检测。如何本地运行验证在仓库根目录执行以下命令即可跑通本题的 Go 解法与全部测试用例go test ./leetcode/weekly/298/d/ -run Test_d -v运行成功后输出类似case -1 is passed以及各用例OK的结果说明题解实现与官方测试数据一致。若只希望运行单个用例可将d_test.go中targetCaseNum改为正数如 1、2、3后再次运行。小结一类二维划分 DP 的通用套路从本题可以提炼出二维区间划分型 DP 的通用模式找子问题第一刀要么不切直接卖要么水平切、要么垂直切切出的两块都是更小尺寸的同构问题定状态f[i][j]表示高i宽j的木块能获得的最大收益列转移对每个方向枚举切点kf[i][j] max(直接价格, f[i][k]f[i][j-k], f[k][j]f[i-k][j])做优化切点枚举到一半即可避免对称重复价格可预写入f数组省去额外存储算复杂度$\mathcal{O}(mn(mn))$ 时间、$\mathcal{O}(mn)$ 空间。该解法在仓库中由 题解文档、Go 实现 与 测试数据 三位一体构成可直接作为后续同类划分/切割问题的参考模板。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐数位 DP 实战解析LeetCode 2719「区间内美丽整数的数目」——以 codeforces-go 仓库的四语言题解与通用模板为参照数位 DP 实战解析LeetCode 2719「区间内美丽整数的数目」——以 codeforces go 仓库的四语言题解与通用模板为参照 本篇文章以算法竞赛科学计算codeforces-go 仓库题解精读LeetCode 2490「环形句子」(Circular Sentence) 多语言实现与测试框架解析codeforces go 仓库题解精读LeetCode 2490「环形句子」 Circular Sentence 多语言实现与测试框架解析 本篇文章精讲 L科学计算codeforces-go 仓库实战LeetCode 1929「数组串联」两种写法的多语言实现与仓库源码验证codeforces go 仓库实战LeetCode 1929「数组串联」两种写法的多语言实现与仓库源码验证 本文以 leetcode/weekly/249/科学计算上一篇PARD-Qwen3-0.6B模型架构详解从Qwen3到PARD优化的完整技术栈下一篇Otto HandlerFinder机制揭秘事件处理器的发现与注册原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考