LeetCode 2312.卖木头块：动态规划(DP)

【LetMeFly】2312.卖木头块：动态规划(DP)

力扣题目链接：https://leetcode.cn/problems/selling-pieces-of-wood/

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [h_i, w_i, price_i] 表示你可以以 price_i 元的价格卖一块高为 h_i 宽为 w_i 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

沿垂直方向按高度完全切割木块，或
沿水平方向按宽度完全切割木块

在将一块木块切成若干小木块后，你可以根据 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⁴
prices[i].length == 3
1 <= h_i <= m
1 <= w_i <= n
1 <= price_i <= 10⁶
所有 (h_i, w_i) 互不相同 。

方法一：动态规划(DP)

令dp[i][j]代表大小为i × j的木块的最大价值。

初始值：若给定的大小为m × n的木块的售卖价格为p则令dp[m][n] = p；否则dp[i][j] = 0。

转移方程：

对于横着切的方法：dp[i][j] = max(dp[i][j], dp[i - k][j] + dp[k][j])（其中 $1\leq k\leq \lfloor \frac{i}{2} \rfloor$ ）
对于竖着切的方法：dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k]);（其中 $1\leq k\leq \lfloor \frac{j}{2} \rfloor$ ）

最终返回dp[m][n]即为答案。

时间复杂度 $O (mn (m + n))$
空间复杂度 $O (mn)$

AC代码

C++

typedef long long ll;
class Solution {
public:
    ll sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<ll>> dp(m + 1, vector<ll>(n + 1));
        for (vector<int>& price : prices) {
            dp[price[0]][price[1]] = price[2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= i / 2; k++) {
                    dp[i][j] = max(dp[i][j], dp[i - k][j] + dp[k][j]);
                }
                for (int k = 1; k <= j / 2; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k]);
                }
            }
        }
        return dp[m][n];
    }
};

Python

from typing import List

class Solution:  # AC,96.77%,100.00%
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        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):
                dp[i][j] = max(
                    dp[i][j],
                    max((dp[i - k][j] + dp[k][j] for k in range(1, i // 2 + 1)), default=0),  # 这里必须加上default，否则可能会变成max(())
                    max((dp[i][j - k] + dp[i][k] for k in range(1, j // 2 + 1)), default=0)
                )
        return dp[m][n]