Leetcode: 2312. Selling Pieces of Wood

Problem Statement: Given a rectangle of dimensions $m \times n$ and tiles $r[i]=[h_i, w_i, p_i]$ where $h_i, w_i$ and $p_i$ are the height, width and price of the $i$th tile, return the maximum coverage (sum of all prices of each tile used) of the given rectangles given that you always have to entirely cut the rectangle in horizontally or vertically.

We can formulate using the following recurrence:

\begin{equation*} f(h, w)=\begin{cases} 0, & \mbox{if $i = 0$ or $j = 0$} \\ \max(p(h, w), f(i, w) + f(h - i, w), f(h, j) + f(h, w - j)) & \mbox{for $1 \leq i < h$ and $1 \leq j < w$>}. \end{cases} \end{equation*}

This recurrence has $O(m \times n)$ subproblems and each one is solved in $O(m + n)$. So, the time complexity to compute it will be $O(m \times n \times (m + n))$.

Top-down

from typing import List
from functools import cache

def solve(m, n, prices):
    p = {}
    hs = set()
    ws = set()

    for h, w, price in prices:
        p[(h, w)] = price
        hs.add(h)
        ws.add(w)

    @cache
    def dfs(h, w):
        if h == 0 or w == 0:
            return 0

        ans = p.get((h, w), 0)
        for new_h in range(1, h):
            if new_h in hs:
                ans = max(ans, dfs(new_h, w) + dfs(h - new_h, w))
        for new_w in range(1, w):
            if new_w in ws:
                ans = max(ans, dfs(h, new_w) + dfs(h, w - new_w))

        return ans

    return dfs(m, n)


assert solve(3, 5, [[1,4,2],[2,2,7],[2,1,3]]) == 19
assert solve(4, 6, [[3,2,10],[1,4,2],[4,1,3]]) == 32
assert solve(200, 200, [[1,1,1000000]]) == 40000000000
assert solve(15, 7, [[14,3,1],[2,2,1],[15,1,1],[8,1,2],[13,5,1],[6,5,1],[13,1,1],[3,3,2]]) == 25


class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        return solve(m, n, prices)