零 标题：算法（，附思维导图 + 全部解法）300题之（2312）卖木头块

一 题目描述

二 解法总览（思维导图）

三 全部解法

面试官：看你准备得差不多了，我们开始面试吧。

狂徒张三：okk~

面试官：题目看得差不多了的话，来说说你的想法、思路哈~

狂徒张三：因为题目中，含有 “最” 字眼，所以我觉得应该优先考虑使用 “动态规划” 。

面试官： 那你觉得使用动态规划的条件有哪些呢？

狂徒张三：我个人认为，应该需要具备2个条件：

1）最优子结构

2）无后效性

面试官： 很好，那你知道动态规划的本质和解题步骤分别是什么吗？

狂徒张三：

1）本质：一种以空间换时间的技术

2）解题步骤：分3步。状态定义： 每个状态的决策，存放每个状态的变量；状态转移方程： 当前状态与之前状态之间的转换关系；初始状态： 初始的状态或者边界条件等。

面试官：小伙子，可以呀。我看你也差不多热完身了，那你就用如上知识解下这道题吧~

旁白：过了5-10分钟，张三迟迟写不出代码。

面试官：（一脸凝重、困惑）难道你只背了相关概念，没进行过相关题目的编码吗？

狂徒张三：（张三面漏怯色）额。。。。

面试官：这样，你把木块想象成大西瓜，写起代码来也会嘎嘎的清凉和爽快哦~
那题目就变成了 —— 你有1个二维（长度为w、宽度为h）的大西瓜，你可以选择直接把它卖掉（若此时得有人正好买长度为w、宽度为h），不然的话此时的大西瓜只能获得0元

狂徒张三：对的，然后我们也可以选择不卖此时的大西瓜，进行横向、纵向的切瓜，把大西瓜不断切成不同的小西瓜，最后从这些切瓜方案中计算出当前大西瓜的能卖处的最大价钱。

面试官：是的，那你这边根据之前所说，写下 状态定义 和 状态转移方程吧~

狂徒张三：好的。

我理解的状态定义 —— dp[i][j]，长度为i、宽度为j时，能得到的最多钱数。

状态转移方程 —— 横向切瓜时：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i - 1]。
纵向切瓜时：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j - 1]。

面试官：那状态的初始化呢？

狂徒张三：根据数组 prices ，进行初始化 —— 当 i、j 存在于 prices 里的0、1下标位置上时，dp[i][j] = prices[对应的元素下标][2]。

面试官：很好，既然思路已经理清了，那就开始你的表演，啊不、开始你的代码编写吧~

旁边：张三瞬间如同任督二脉被打通，三下五除二，不到10分钟便把代码敲打了出来~

1 方案1

1)代码：

// 方案1 “动态规划法 - 普通版”。
// “技巧：题干中含有 最 字眼，优先考虑动态规划（本质：以空间换时间的技术）。”
// 参考：
// 1）https://牛客.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-牛客-solution-gflg/
// 2）https://牛客.cn/problems/selling-pieces-of-wood/solution/by-endlesscheng-mrmd/

// 想法（这里把木块想象成大西瓜，写起代码来也会嘎嘎的清凉和爽快哦~）：
// 1）状态定义：dp[i][j]，长度为i、宽度为j时，能得到的最多钱数。
// 2）状态转移：
// 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i - 1]。
// 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j - 1]。

// 思路：
// 1.1）状态初始化：l = prices.length; 
// dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
// 思考：二维的每个元素为啥都先 默认填充0 ？
// 1.2）状态初始化：遍历 数组 prices ，进一步初始化 数组 dp 。

// 2）核心：状态转移。
// 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i - 1]。
// 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j - 1]。

// 3）返回结果 dp[m][n] 。
var sellingWood = function(m, n, prices) {
    // 1.1）状态初始化：l = prices.length; 
    // dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
    // 思考：二维的每个元素为啥都先 默认填充0 ？
    const l = prices.length;
    let dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));

    // 1.2）状态初始化：遍历 数组 prices ，进一步初始化 数组 dp 。
    for (let i = 0; i < l; i++) {
        const [width, height, price] = prices[i];
        dp[width][height] = price;
    }

    // 2）核心：状态转移。
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i - 1]。
            for (let k = 1; k < i; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
            // 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j - 1]。
            for (let k = 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }

    // 3）返回结果 dp[m][n] 。
    return dp[m][n];
};

2 方案2

面试官：Good。代码结构很有层次感，注释也放在了很合适的位置~

狂徒张三：毕竟这个“二维的大西瓜”是保熟的，我敢保证这里的算法一定是最优的，能够保证我们的大西瓜卖出最高的价钱。

面试官：你确定你这个“大西瓜切割算法”保熟吗？我看不一定吧？

狂徒张三：我是1个正经的算法人，还能给你写法“生瓜算法”不成？

面试官：我问你，这“大西瓜切割算法”保熟吗？

狂徒张三：你就说我这次面试能不能过吧~

面试官：

狂徒张三：那我在看看、想想优化点吧

旁白：只见张三在纸上齐飕飕的写起了代码运行过程。
...
dp[5][5] = max(dp[5][5], dp[1][5] + dp[4][5], dp[2][5] + dp[3][5], dp[3][5] + dp[2][5], dp[2][5] + dp[1][5])
...

狂徒张三：看起来确实有优化点 —— 存在大量的冗余计算，我们下标k只需枚举到一半的位置即可 —— 即 k的范围为 [1, i / 2（向下取整）] 。

1)代码：

// 方案2 “动态规划法 - 优化版”。
// “技巧：题干中含有 最 字眼，优先考虑动态规划（本质：以空间换时间的技术）。”
// 参考：
// 1）https://牛客.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-牛客-solution-gflg/
// 2）https://牛客.cn/problems/selling-pieces-of-wood/solution/by-endlesscheng-mrmd/

// 想法（这里把木块想象成大西瓜，写起代码来也会嘎嘎的清凉和爽快哦~）：
// 1）状态定义：dp[i][j]，长度为i、宽度为j时，能得到的最多钱数。
// 2）状态转移：
// 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i - 1]。
// 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j - 1]。

// 思路：
// 1.1）状态初始化：l = prices.length; 
// dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
// 思考：二维的每个元素为啥都先 默认填充0 ？
// 1.2）状态初始化：遍历 数组 prices ，进一步初始化 数组 dp 。

// 2）核心：状态转移（有优化，存在对称性，k枚举到i、j的1半的位置即可）。
// 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i / 2（向下取整）]。
// 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j / 2（向下取整）]。

// 3）返回结果 dp[m][n] 。
var sellingWood = function(m, n, prices) {
    // 1.1）状态初始化：l = prices.length; 
    // dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));
    // 思考：二维的每个元素为啥都先 默认填充0 ？
    const l = prices.length;
    let dp = new Array(m + 1).fill(1).map(v => new Array(n + 1).fill(0));

    // 1.2）状态初始化：遍历 数组 prices ，进一步初始化 数组 dp 。
    for (let i = 0; i < l; i++) {
        const [width, height, price] = prices[i];
        dp[width][height] = price;
    }

    // 2）核心：状态转移。
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 2.1）横向切：dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j])，k的范围为 [1, i / 2（向下取整）]。
            for (let k = 1; k <= Math.floor(i / 2); k++) {
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
            // 2.2）纵向切：dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k])，k的范围为 [1, j / 2（向下取整）]。
            for (let k = 1; k <= Math.floor(j / 2); k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[i][j - k]);
            }
        }
    }

    // 3）返回结果 dp[m][n] 。
    return dp[m][n];
};

旁白：张三写完了如上代码，急忙问面试官。

狂徒张三：通过面试了吧？

面试官：

狂徒张三：

又1个offer，然后马上就要出任 CEO 了，我晚上应该是去吃 沙县小吃 呢？ 还是 兰州拉面 呢？哎，选择太多也是一种烦恼！

四 资源分享 & 更多

1 历史文章 - 总览

2 博主简介

码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 牛客 ~