题目
You are given two integers m
and n
that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array prices
, where prices[i] = [hi, wi, pricei]
indicates you can sell a rectangular piece of wood of height hi
and width wi
for pricei
dollars.
To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to prices
. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width.
Return the maximum money you can earn after cutting an m x n
piece of wood.
Note that you can cut the piece of wood as many times as you want.
Example 1:

Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]] Output: 19 Explanation: The diagram above shows a possible scenario. It consists of: - 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14. - 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3. - 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2. This obtains a total of 14 + 3 + 2 = 19 money earned. It can be shown that 19 is the maximum amount of money that can be earned.
Example 2:

Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]] Output: 32 Explanation: The diagram above shows a possible scenario. It consists of: - 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30. - 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2. This obtains a total of 30 + 2 = 32 money earned. It can be shown that 32 is the maximum amount of money that can be earned. Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.
Constraints:
1 <= m, n <= 200
1 <= prices.length <= 2 * 104
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 106
- All the shapes of wood
(hi, wi)
are pairwise distinct.
思路
题目大意是切木板,每次只能横切或竖切,切成特定的形状可以获得收益,求收益最大值。
相信大家看到这题想到的就是动规,因为木板切割以后,每块木板都是一个单独的子问题,下面我们的问题就是状态转移关系了。
然而,这道题的时间卡的很紧的,和最优解法稍微有偏离就很容易超时。
一些失败的尝试
v1.backtracing + memorization,每次取prices中的形状,尝试横切和竖切。
第一反应就是这个,提交上去超时了。
代码如下。
import collections
class Solution(object):
def sellingWood(self, m, n, prices):
m1 = collections.defaultdict(list)
for x, y, p in prices:
m1[x].append((y, p))
xs = sorted(m1.keys())
for x in m1:
m1[x] = sorted(m1[x], key=lambda tp:tp[0])
_m = {}
def f(m, n):
if m == 0 or n == 0:
return 0
elif (m, n) in _m:
return _m[(m, n)]
ret = 0
for x, y, p in prices:
# 横切
if x <= m and y <= n:
cur_ans = p + f(x, n - y) + f(m - x, n)
ret = max(cur_ans, ret)
# 竖切
cur_ans = p + f(m - x, y) + f(m, n - y)
ret = max(cur_ans, ret)
_m[(m, n)] = ret
return ret
return f(m, n)
时间复杂度O(m*n*prices),仔细看下数据规模,prices在10^6数量级,超时可以理解。
v2.backtracing + memorization,每次取prices中的x值和y值,尝试横切和竖切。
分析下刚才的思路,按照prices每种形状切,其实是有很多冗余的。两个形状的x相同,只切一次就好了。
这好办,我们取prices中的x和y取个unique,每次切直接遍历这个x和y就可以了。
时间复杂度O(m2 * n2)
代码如下。
import collections
class Solution(object):
def sellingWood(self, m, n, prices):
xs = sorted(set([tp[0] for tp in prices]))
ys = sorted(set([tp[1] for tp in prices]))
mp = {(x, y): p for x, y, p in prices}
_m = {}
def dp(m, n):
if m == 0 or n == 0:
return 0
elif (m, n) in _m:
return _m[(m, n)]
ret = mp[(m, n)] if (m, n) in mp else 0
for x in xs:
if x >= m:
break
ret = max(ret, dp(x, n) + dp(m - x, n))
for y in ys:
if y >= n:
break
ret = max(ret, dp(m, y) + dp(m, n - y))
_m[(m, n)] = ret
return ret
return dp(m, n)
提交上去还是超时了。
事后再想想,这个思路应该可行,改下递推应该就可以,原因见最终版本。
小聪明,去掉冗余的prices
顺着上面的思路来,超时了看起来是prices太多了,如果我们能去掉一些,就能在每轮backtracing时少做一些迭代了。
如果两个shape,shape1=(x1, y1, p1), shape2=(x2, y2, p2)满足x1 <= x2 && y1 <= y2 && p1 >= p2,我们就可以直接把shape2去掉了——遇到shape2直接切成shape1会赚更多的钱,还有机会切出更多的木板。
代码略,去冗余的时间复杂度为O(len(prices)2)——考虑到prices的规模,是个很危险的复杂度——当然要是真有效果,还可以接受。
效果嘛,在某些测试样例上很有效——可以把prices从20W降低到几十。
提交上去,发现leetcode构造了一组贼变态的case,大概如下图。

在这组case下面,完全没有可以去掉的prices嘛。
事实证明这个小聪明白耍了,下面我们来看看标准解法。
最终版本
对于m*n的木板直接暴力尝试横切(1~m – 1)和竖切(1~n – 1)的组合就好了。在k处横切一刀,收益为dp[m – k][n] + dp[k][n];在w处竖切一刀,收益为dp[m][n – w] + dp[m][w],在加上不切(prices[i][j])的收益,取最大值即可。
这个方法比v2好在哪里呢?暴力搜索时分别尝试切到一半就行了(m//2, n // 2),因为在切过去是对称的,总时间会略低一点。当然效果还是要看case数据分布。当然更更重要还是后面的递归改递推。
状态方程如下,dp[i][j] = max(prices[i][j], dp[i – k][j] + dp[i][j], dp[i][j – w] + dp[i][w]), 1<=k <=i //2, 1 <= w <= j // 2
backtracing版本如下。
class Solution5(object):
def sellingWood(self, m, n, prices):
mp = {(x, y): p for x, y, p in prices}
_m = {}
def dp(m, n):
if m == 0 or n == 0:
return 0
elif (m, n) in _m:
return _m[(m, n)]
ret = mp[(m, n)] if (m, n) in mp else 0
for x in range(1, m // 2 + 1):
ret = max(ret, dp(x, n) + dp(m - x, n))
for y in range(1, n // 2 + 1):
ret = max(ret, dp(m, y) + dp(m, n - y))
_m[(m, n)] = ret
return ret
return dp(m, n)
提交上去还是超时。递推改递归后,代码如下。
class Solution(object):
def sellingWood(self, m, n, prices):
dp = [[0] * (n + 1) for _ in range(m + 1)]
for x, y, p in prices:
dp[x][y] = p
for i in range(1, m + 1):
for j in range(1, n + 1):
val = 0
for k in range(1, i // 2 + 1):
val = max(val, dp[k][j] + dp[i - k][j])
for k in range(1, j // 2 + 1):
val = max(val, dp[i][k] + dp[i][j - k])
dp[i][j] = max(val, dp[i][j])
return dp[-1][-1]
略意外的是,同一组测试样例下面,backtracing+memorization的效率居然和递推差这么多。按以前的经验,一般递推法dp会比回溯快50%左右。谨慎推测是这道题状态空间是稠密的,且递归栈实在太深了。

提交上去,终于AC了。

收工!
——此处是内容的分割线——
除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接
本文链接:https://www.utopiafar.com/2022/06/24/leetcode-2312-selling-pieces-of-wood/
码字不易,如果觉得内容有帮助,欢迎留言or点赞!