Hard

题目描述

给你两个整数 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 * 10^4
  • prices[i].length == 3
  • 1 <= hi <= m
  • 1 <= wi <= n
  • 1 <= pricei <= 10^6
  • 所有 (hi, wi) 互不相同。

解题思路

这是一道经典的区间动态规划问题。我们需要考虑对于任意大小的木材块，如何获得最大收益。

基本思路： 对于一块 m × n 的木材，我们有三种选择：

  1. 直接出售（如果价格表中有对应规格）
  2. 水平切割：分成 i × n 和 (m-i) × n 两块
  3. 垂直切割：分成 m × j 和 m × (n-j) 两块

我们需要在所有可能的选择中找到收益最大的方案。

动态规划设计：

  • 状态定义：dp[i][j] 表示切割 i × j 大小的木材能获得的最大收益
  • 状态转移：
    • 直接出售：dp[i][j] = price[i][j]（如果存在）
    • 水平切割：dp[i][j] = max(dp[k][j] + dp[i-k][j])，其中 1 ≤ k < i
    • 垂直切割：dp[i][j] = max(dp[i][k] + dp[i][j-k])，其中 1 ≤ k < j
  • 初始状态：dp[0][j] = dp[i][0] = 0

优化考虑： 使用记忆化搜索可以避免重复计算，提高效率。我们先建立价格映射表，然后递归求解每个子问题。

代码实现

class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        // 建立价格映射表
        unordered_map<int, unordered_map<int, int>> priceMap;
        for (auto& price : prices) {
            priceMap[price[0]][price[1]] = price[2];
        }
        
        // 记忆化数组
        vector<vector<long long>> memo(m + 1, vector<long long>(n + 1, -1));
        
        function<long long(int, int)> dfs = [&](int h, int w) -> long long {
            if (h == 0 || w == 0) return 0;
            if (memo[h][w] != -1) return memo[h][w];
            
            long long result = 0;
            
            // 直接出售
            if (priceMap.count(h) && priceMap[h].count(w)) {
                result = priceMap[h][w];
            }
            
            // 水平切割
            for (int i = 1; i < h; i++) {
                result = max(result, dfs(i, w) + dfs(h - i, w));
            }
            
            // 垂直切割
            for (int j = 1; j < w; j++) {
                result = max(result, dfs(h, j) + dfs(h, w - j));
            }
            
            return memo[h][w] = result;
        };
        
        return dfs(m, n);
    }
};

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        # 建立价格映射表
        price_map = {}
        for h, w, price in prices:
            price_map[(h, w)] = price
        
        # 记忆化装饰器
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(h, w):
            if h == 0 or w == 0:
                return 0
            
            result = 0
            
            # 直接出售
            if (h, w) in price_map:
                result = price_map[(h, w)]
            
            # 水平切割
            for i in range(1, h):
                result = max(result, dfs(i, w) + dfs(h - i, w))
            
            # 垂直切割
            for j in range(1, w):
                result = max(result, dfs(h, j) + dfs(h, w - j))
            
            return result
        
        return dfs(m, n)

public class Solution {
    public long SellingWood(int m, int n, int[][] prices) {
        // 建立价格映射表
        var priceMap = new Dictionary<(int, int), int>();
        foreach (var price in prices) {
            priceMap[(price[0], price[1])] = price[2];
        }
        
        // 记忆化数组
        var memo = new long[m + 1][];
        for (int i = 0; i <= m; i++) {
            memo[i] = new long[n + 1];
            Array.Fill(memo[i], -1);
        }
        
        long Dfs(int h, int w) {
            if (h == 0 || w == 0) return 0;
            if (memo[h][w] != -1) return memo[h][w];
            
            long result = 0;
            
            // 直接出售
            if (priceMap.ContainsKey((h, w))) {
                result = priceMap[(h, w)];
            }
            
            // 水平切割
            for (int i = 1; i < h; i++) {
                result = Math.Max(result, Dfs(i, w) + Dfs(h - i, w));
            }
            
            // 垂直切割
            for (int j = 1; j < w; j++) {
                result = Math.Max(result, Dfs(h, j) + Dfs(h, w - j));
            }
            
            return memo[h][w] = result;
        }
        
        return Dfs(m, n);
    }
}

var sellingWood = function(m, n, prices) {
    const priceMap = new Map();
    for (const [h, w, price] of prices) {
        priceMap.set(h * 1000 + w, price);
    }
    
    const memo = new Map();
    
    function dp(h, w) {
        if (h === 0 || w === 0) return 0;
        
        const key = h * 1000 + w;
        if (memo.has(key)) return memo.get(key);
        
        let maxProfit = priceMap.get(key) || 0;
        
        for (let i = 1; i < h; i++) {
            maxProfit = Math.max(maxProfit, dp(i, w) + dp(h - i, w));
        }
        
        for (let j = 1; j < w; j++) {
            maxProfit = Math.max(maxProfit, dp(h, j) + dp(h, w - j));
        }
        
        memo.set(key, maxProfit);
        return maxProfit;
    }
    
    return dp(m, n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m²n + mn²)，其中 m 和 n 分别是木材的高度和宽度。对于每个状态 (i,j)，我们需要尝试所有可能的切割位置
空间复杂度O(mn)，用于存储记忆化数组和价格映射表

相关题目