class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
"""
动态规划
dp[x,y]表示 高、宽为x,y时可以得到的最多钱数
情况1: 当x,y存在于prices中的木块大小
dp[xi,yi] = prices[i]
情况2: 当高x>1时，可以水平切割
dp[x,y] = max(dp[i,y]+dp[x-i, y], x in [1, x-1])
情况3: 当宽y>1时，可以垂直切割
dp[x,y] = max(dp[x,j]+dp[x, y-j]), y in [1, y-1])
"""
# vals = {}
# @cache
# def dfs(x, y):
# ret = vals.get((x,y), 0)
# if x > 1:
# for i in range(1, x//2+1):
# ret = max(ret, dfs(i, y)+dfs(x-i, y))
# if y > 1:
# for j in range(1, y//2+1):
# ret = max(ret, dfs(x, j) + dfs(x, y-j))
# return ret
dp = [ [0]*(n+1) for _ in range(m+1)]
for (h, w, price) in prices:
dp[h][w] = price
ret = 0
optimized_split_height_per_width = [[] for _ in range(n+1)]
for i in range(1, m+1):
optimized_split_width_per_height = []
for j in range(1, n+1):
tmp = dp[i][j]
height_optimized = True
width_optimized = True
# 水平切割，剪枝，并不是所有位置都需要枚举
# 只需要枚举之前的最后分割点即可，之前没有进行分割的点，后面用不到
for split_h in optimized_split_height_per_width[j]:
val = dp[split_h][j]+dp[i-split_h][j]
if val > tmp:
# 当前宽高是[i, j]，可以进行水平分割
# 分割高度是split_h
# 记录下来，当高为i时，可以枚举这个宽度
tmp = val
height_optimized = False
width_optimized = True
elif val == tmp:
height_optimized = False
# 垂直切割，剪枝，并不是所有位置都需要枚举
for split_w in optimized_split_width_per_height:
val = dp[i][split_w]+dp[i][j-split_w]
if val > tmp:
# 当前宽高是[i, j]，可以进行垂直分割
# 分割宽度是split_w
# 记录下来，当宽为j时，可以枚举这个高度
tmp = val
width_optimized = False
height_optimized = True
elif val == tmp:
width_optimized = False
if tmp == 0:
width_optimized = height_optimized = False
dp[i][j] = tmp
if width_optimized:
optimized_split_width_per_height.append(j)
if height_optimized:
optimized_split_height_per_width[j].append(i)
ret = dp[-1][-1]
return ret
Explain
此题采用动态规划的方法来解决。定义 dp[x][y] 为当木块尺寸为 x 高和 y 宽时可以获得的最大收益。初始化 dp 数组时，先将所有给定的价格设置到对应的尺寸上。接下来，对于每个尺寸的木块，尝试进行水平和垂直的切割，更新 dp[x][y] 为所有可能的切割方式中的最大值。通过维护 optimized_split_height_per_width 和 optimized_split_width_per_height 两个列表来记录对于每个尺寸的木块，之前有效的切割位置，从而减少不必要的重复计算，优化动态规划过程。最终 dp[m][n] 存储的就是切割大小为 m x n 的木块能得到的最多钱数。
时间复杂度: O(m^2 * n + m * n^2)
空间复杂度: O(m * n)
class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
# Initialize dp table with all zeros
dp = [[0]*(n+1) for _ in range(m+1)]
# Set prices in dp table
for (h, w, price) in prices:
dp[h][w] = price
# Initialize lists to store optimized split positions
optimized_split_height_per_width = [[] for _ in range(n+1)]
for i in range(1, m+1):
optimized_split_width_per_height = []
for j in range(1, n+1):
tmp = dp[i][j]
height_optimized = width_optimized = True
# Horizontal cuts
for split_h in optimized_split_height_per_width[j]:
val = dp[split_h][j]+dp[i-split_h][j]
if val > tmp:
tmp = val
height_optimized = False
elif val == tmp:
height_optimized = False
# Vertical cuts
for split_w in optimized_split_width_per_height:
val = dp[i][split_w]+dp[i][j-split_w]
if val > tmp:
tmp = val
width_optimized = False
elif val == tmp:
width_optimized = False
# Update dp table and optimized lists
dp[i][j] = tmp
if width_optimized:
optimized_split_width_per_height.append(j)
if height_optimized:
optimized_split_height_per_width[j].append(i)
# Return the maximum possible money from cutting m x n wood block
return dp[m][n]
