2312.卖木头块

链接：2312.卖木头块
难度：Hard
标签：记忆化搜索、数组、动态规划
简介：请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。

题解 1 - python

• 编辑时间：2024-03-15
• 执行用时：6046ms
• 内存消耗：38.27MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        price_map = {}
        for k1, k2, price in prices:
            if k1 not in price_map: price_map[k1] = {}
            item_map = price_map[k1]
            if k2 not in item_map: item_map[k2] = price
        @cache
        def dfs(m: int, n: int) -> int:
            ans = 0
            if m in price_map and n in price_map[m]:
                ans += price_map[m][n]
            for i in range(1, m):
                ans = max(ans, dfs(i, n) + dfs(m - i, n))
            for i in range(1, n):
                ans = max(ans, dfs(m, i) + dfs(m, n - i))
            return ans
        return dfs(m, n)