关于javascript:2312卖木头块-面试官与狂徒张三的那些事leetcode附思维导图-全部解法

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

一 题目形容

二 解法总览（思维导图）

三 全副解法

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

狂徒张三：okk~

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

狂徒张三：因为题目中，含有 “最” 字眼，所以我感觉应该优先思考应用 “动静布局”。

面试官：那你感觉应用动静布局的条件有哪些呢？

狂徒张三：我集体认为，应该须要具备 2 个条件：

**1）最优子结构

2）无后效性
**

面试官：很好，那你晓得动静布局的实质和解题步骤别离是什么吗？

狂徒张三：

**1）实质：一种以空间换工夫的技术

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

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

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

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

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

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

狂徒张三：对的，而后咱们也能够抉择不卖此时的大西瓜，进行横向、纵向的切瓜，把大西瓜一直切成不同的小西瓜，最初从这些切瓜计划中计算出以后大西瓜的能卖处的最大价格。

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

狂徒张三：好的。

我了解的状态定义 —— dpi，长度为 i、宽度为 j 时，能失去的最多钱数。

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

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

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

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

旁边：张三霎时如同任督二脉被买通，三下五除二，不到 10 分钟便把代码敲打了进去~

1 计划 1

1)代码：

// 计划 1“动静规划法 - 一般版”。//“技巧：题干中含有 最 字眼，优先思考动静布局（实质：以空间换工夫的技术）。”// 参考：// 1）https://leetcode.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-leetcode-solution-gflg/
// 2）https://leetcode.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 个正经的算法人，还能给你写法“生瓜算法”不成？

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

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

面试官：

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

旁白：只见张三在纸上齐飕飕的写起了代码运行过程。
…
dp5 = max(dp5, dp1 + dp4, dp2 + dp3, dp3 + dp2, dp2 + dp1)
…

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

1)代码：

// 计划 2“动静规划法 - 优化版”。//“技巧：题干中含有 最 字眼，优先思考动静布局（实质：以空间换工夫的技术）。”// 参考：// 1）https://leetcode.cn/problems/selling-pieces-of-wood/solution/mai-mu-tou-kuai-by-leetcode-solution-gflg/
// 2）https://leetcode.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 博主简介

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