题目
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 <= 2001 <= prices.length <= 2 * 104prices[i].length == 31 <= hi <= m1 <= wi <= n1 <= 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点赞！