第六章 - 高频考题(困难)
5254. 卖木头块

题目地址(5254. 卖木头块)

https://leetcode.cn/problems/selling-pieces-of-wood/

题目描述

给你两个整数 m 和 n ,分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ,其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每一次操作中,你必须按下述方式之一执行切割操作,以得到两块更小的矩形木块:
沿垂直方向按高度 完全 切割木块,或
沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后,你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。
请你返回切割一块大小为 m x n 的木块后,能得到的 最多 钱数。
注意你可以切割木块任意次。
示例 1:
输入:m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出:19
解释:上图展示了一个可行的方案。包括:
- 2 块 2 x 2 的小木块,售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块,售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块,售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。
示例 2:
输入:m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出:32
解释:上图展示了一个可行的方案。包括:
- 3 块 3 x 2 的小木块,售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块,售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。
提示:
1 <= m, n <= 200
1 <= prices.length <= 2 * 104
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 106
所有 (hi, wi) 互不相同 。

前置知识

  • 动态规划记忆化递归

公司

  • 暂无

思路

这是一个经典的枚举割点的动态规划问题。
相关题目有铺地毯/瓷砖,本质都是给你一个二维矩阵,给你一堆价值,让你求如何分割价值最小或最大。
可以这么做的前提是如果我们可以切割,那么切割后会变为两个子矩阵,这两个子矩阵和切割前除了大小不一样,其他都一样。因此可以不断枚举割点,递归解决。
定义 dp[i][j] 为切割长度为 i 宽度为 j 的木板的最大价格,那么答案就是 dp[m,n]
接下来,我们枚举横着切的切点和竖着切的切点就可以得到答案。
切割前我们有三种选择:
  1. 1.
    横着切,切哪呢?枚举所有可能。因为横着切本质是高度变了,宽度不变,因此枚举所有可能就是枚举高度为 [1,i-1](其中 i 为当前木板高度)
  2. 2.
    竖着切,同理
  3. 3.
    不切。
取三种情况的最大值即可。

关键点

  • 枚举切割点

代码

  • 语言支持:Python3
Python3 Code:
class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
d = {(h, w): p for h, w, p in prices}
@cache
def dp(i, j):
ans = d.get((i, j), 0) # 不切
# 竖着切
for x in range(1, i):
ans = max(ans, dp(x, j) + dp(i - x, j))
# 横着切
for y in range(1, j):
ans = max(ans, dp(i, y) + dp(i, j - y))
return ans # 且三种选择的最大值即可
return dp(m, n)
复杂度分析
令 t 为 prices 长度。
  • 时间复杂度:$O(n * m * (n + m))$
  • 空间复杂度:$O(t + n * m)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。