给你两个整数 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 元是最多能得到的钱数。）

提示：

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 104
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 106
• 所有 (hi, wi) 互不相同 。

解法一：（记忆化深搜）

from functools import cache
# 记忆化深搜
class Solution:
    def sellingWood(self, m, n, prices):
        value = dict()

        @cache
        def dfs(x, y):
            ret = value.get((x, y), 0)

            if x > 1:
                for i in range(1, x):
                    ret = max(ret, dfs(i, y) + dfs(x - i, y))
            
            if y > 1:
                for j in range(1, y):
                    ret = max(ret, dfs(x, j) + dfs(x, y - j))
            return ret
        
        for (h, w, price) in prices:
            value[(h, w)] = price
        
        ans = dfs(m, n)
        dfs.cache_clear()
        return ans

# m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
obj = Solution()
obj.sellingWood(3,5,[[1,4,2],[2,2,7],[2,1,3]])

解法二：（dp）

from typing import List

# dp
class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        dp = [[0 for i in range(n + 1)] for j in range(m + 1)]#初始化所有木块价格为0
        for h, w, p in prices:#将价格列表填充至dp
            dp[h][w] = p
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                for x in range(1, i):#高度切割
                    dp[i][j] = max(dp[i][j], dp[x][j] + dp[i - x][j])
                for x in range(1, j):#宽度切割
                    dp[i][j] = max(dp[i][j], dp[i][x] + dp[i][j - x])
        return dp[m][n]

# m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
obj = Solution()
obj.sellingWood(3,5,[[1,4,2],[2,2,7],[2,1,3]])