2022-09-13：给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以

2022 年 9 月 13 日
北京
本文字数：1314 字
阅读完需：约 4 分钟

2022-09-13：给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei]表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：沿垂直方向按高度完全切割木块，或沿水平方向按宽度完全切割木块在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你不能旋转切好后木块的高和宽。请你返回切割一块大小为 m x n 的木块后，能得到的最多钱数。注意你可以切割木块任意次。输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]。输出：32。

答案 2022-09-13：

严格位置依赖的动态规划版本 + 优化。优化 1 : 递归的形式，改成迭代形式；优化 2 : prices 中的单块收益直接填入 dp 表即可，如果有更好的分割方案，更新掉；优化 3 : 分割只需要枚举一半即可。时间复杂度：O(N3)。空间复杂度：O(N2)。

代码用 rust 编写。代码如下：

fn main() {    let mut arr = vec![vec![3, 2, 10], vec![1, 4, 2], vec![4, 1, 3]];    let ans = selling_wood3(4, 6, &mut arr);    println!("ans = {}", ans);}
fn selling_wood3(m: i64, n: i64, prices: &mut Vec<Vec<i64>>) -> i64 {    // dp表！    let mut dp: Vec<Vec<i64>> = vec![];    for i in 0..m + 1 {        dp.push(vec![]);        for _ in 0..n + 1 {            dp[i as usize].push(0);        }    }    for p in prices.iter() {        // {3, 5, 100}        // 0 1 2        // dp[3][5] = 100        dp[p[0] as usize][p[1] as usize] = p[2];    }    for i in 1..=m {        for j in 1..=n {            // 垂直分割            // i * j = 100 * 100            // dp[100][1] + dp[100][99]            // dp[100][2] + dp[100][98]            // ..            for k in 1..=(j >> 1) {                dp[i as usize][j as usize] = get_max(                    dp[i as usize][j as usize],                    dp[i as usize][k as usize] + dp[i as usize][(j - k) as usize],                );            }            // 水平分割            // 100 * 100            // 1) 1 * 100 + 99 * 100            // 1) 2 * 100 + 98 * 100            // i * j            // 1) 1 * j + (i - 1) * i;            // 2) 2 * j + (i - 2) * j;            // k) k * j + (i - k) * j;            for k in 1..=(i >> 1) {                dp[i as usize][j as usize] = get_max(                    dp[i as usize][j as usize],                    dp[k as usize][j as usize] + dp[(i - k) as usize][j as usize],                );            }        }    }    return dp[m as usize][n as usize];}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}