算法leetcode

【二维线性DP】力扣2312-卖木头块

字数统计: 1.6k字   |   阅读时长: 6分
,

摘要: 一个二维线性 DP 的比较困难题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们看一个二维线性 DP 的问题。DP 状态有两个维度，这里的两个维度都是附加信息，状态的推导过程依赖于附加信息而不依赖于阶段。因此作为阶段的切割次数并不出现在 DP 状态的维度中。这与常见的动态规划的 DP 状态中有某个维度是阶段的情况不同。

题目

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

题解

算法: 二维线性DP

按照题目描述。每切一刀都必须完整切割，不允许只切割到一半就停下，因此对于一块长方形木块，切一刀之后就一定得到两块更小的长方形木块，不会出现其它形状。

因此我们只需要考虑各种大小的长方形木块的情况即可。定义 $dp[i][j]$ 表示高度 $i$ 宽度 $j$ 的木块最终可以卖得的最多钱数。每个状态 $(i, j)$ 都代表一个子问题。

这类值得注意的一个点是阶段的意义并不非常明显。按照此前解决常见的 DP 问题的理解，阶段往往具有位置、时间、步数等物理含义，一个阶段一个阶段地往前推导阶段即可得到所有的状态。

在这里如果做类似考虑，阶段应该是切割的步数，木块的高和宽 $(i, j)$ 是附加信息，比如第 1 阶段的状态是 $(m, n)$，切割一刀后，进入第 2 阶段，可能的状态取决于从哪里切割，然后以此类推。

这样 $dp$ 数组的各个维度均为附加信息，并不像通常的有某个维度表示阶段的情况。因此在推导状态 $dp[i][j]$ 的过程中，阶段的概念隐藏起来了。这种阶段不出现在 dp 数组某个维度中的状态设计，在一些用动态规划解决的数学问题中经常见到。以后可以专门做个汇总。

下面我们来考虑状态转移方程。对于 $(i, j)$，有按照高度和按照宽度两种切法：

  • 按照高度 $h$ 切割，将得到两块宽度均为 $j$，高度分别为 $h$ 和 $i - h$ 的两块木板，状态转移到 $(h, j)$ 和 $(i - h, j)$。$h$ 可以取 $1, 2, \cdots, \left\lfloor\frac{i}{2}\right\rfloor$。
  • 按照宽度 $w$ 切割，将得到两块高度均为 $i$，宽度分别为 $w$ 和 $j - w$ 的两块木板，状况转移到 $(i, w)$ 和 $(i, j - w)$。$w$ 可以取 $1, 2, \cdots, \left\lfloor\frac{j}{2}\right\rfloor$。

于是：

最后一个问题就是初始值的问题。对于 $(1, 1)$，这是最小的单元，无法继续切割，如果 $prices$ 数组中有记录 $(1, 1)$ 卖出的价钱，记其为 $p[1][1]$，则 $dp[1][1] = p[1][1]$。

对于一般的 $(i, j)$ 来说，如果要切一刀的话，那么就按上述公式进行状态转移，此外如果 $prices$ 数组中有记录 $(i, j)$ 卖出的价钱，记其为 $p[i][j]$，则 $dp[i][j]$ 还有一种可能性就是 $p[i][j]$。

因此我们可以首先将 $dp[i][j]$ 初始化为 $p[i][j]$，然后再进行状态的推导即可。

共 $mn$ 个状态，每个状态都需要推导一次，一次状态转移最多可能到达 $m + n$ 个下一阶段的状态。因此总时间复杂度为 $O(mn(m+n))$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        self.p = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i, j, price in prices:
            self.p[i][j] = price
        return self.solve(m, n)

    @functools.lru_cache(int(1e8))
    def solve(self, i: int, j: int) -> int:
        ans = self.p[i][j]
        for h in range(1, i // 2 + 1):
            ans = max(ans, self.solve(h, j) + self.solve(i - h, j))
        for w in range(1, j // 2 + 1):
            ans = max(ans, self.solve(i, w) + self.solve(i, j - w))
        return ans
Share