LeetCode 2312 - Selling Pieces of Wood

The problem presents a rectangular piece of wood of size m x n and a list of specific prices for certain subrectangles. Each entry in the prices array, [hi, wi, pricei], indicates that a piece of wood of height hi and width wi can be sold for pricei dollars.

leetcodehardarraydynamic-programmingmemoization

LeetCode Problem 2312

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Memoization

Solution

Problem Understanding

The problem presents a rectangular piece of wood of size m x n and a list of specific prices for certain subrectangles. Each entry in the prices array, [hi, wi, pricei], indicates that a piece of wood of height hi and width wi can be sold for pricei dollars. You may make any number of horizontal or vertical cuts across the full height or width of a piece to divide it into smaller pieces. The key point is that the wood pieces cannot be rotated, meaning a 2 x 3 piece is not equivalent to a 3 x 2 piece. After cutting, you may sell any pieces according to the price list, and multiple identical pieces can be sold.

The goal is to maximize the total money obtained from a piece of wood of size m x n.

Inputs are bounded by 1 <= m, n <= 200 and up to 2 * 10^4 price entries. This indicates that a brute-force recursive approach without caching will likely be too slow due to exponential splitting possibilities. The problem guarantees that each (hi, wi) pair is distinct and all prices are positive integers.

Important edge considerations include: if a piece matches a priced shape exactly, selling it may be optimal; small or prime dimensions may limit cutting options; and some pieces may not be sold directly but could be used as part of optimal cuts.

Approaches

A brute-force approach would recursively try every possible vertical and horizontal cut for a piece of wood, compute the maximum revenue for each resulting piece, and combine the results. While correct, this approach quickly becomes infeasible due to exponential combinations, especially since m and n can be up to 200.

The key insight for optimization is that the problem exhibits overlapping subproblems. The maximum revenue for a subrectangle depends only on its dimensions and the price list. Therefore, we can use dynamic programming with memoization, storing the maximum revenue for each (height, width) subrectangle. By doing this, each subproblem is computed at most once, drastically reducing redundant computation.

We maintain a memoization table mapping (height, width) to the maximum obtainable price. For each rectangle, we first consider if selling it directly is profitable and then recursively try all horizontal and vertical cuts, combining the subresults to find the maximum.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(1) Exponential recursive splitting; infeasible for m, n up to 200
Optimal (DP + Memoization) O(m * n * (m + n)) O(m * n + p) Computes each subrectangle once; tries all horizontal and vertical cuts; p = number of prices

Algorithm Walkthrough

  1. Preprocess Prices: Store the prices in a hash map or dictionary keyed by (height, width) for constant-time lookups. This allows quick access to the price of a rectangle if it matches a listed shape.
  2. Initialize Memoization Table: Create a dictionary dp where dp[(h, w)] will store the maximum revenue obtainable for a rectangle of height h and width w.
  3. Define Recursive Function: Implement a function dfs(h, w) that returns the maximum revenue for a rectangle of dimensions h x w.
  4. Base Case: If (h, w) is in the price map, set the initial maximum revenue to price_map[(h, w)]. Otherwise, start with zero.
  5. Try Horizontal Cuts: For every possible horizontal cut i from 1 to h-1, split the rectangle into (i x w) and (h-i x w), and recursively compute their revenues. Update the maximum revenue.
  6. Try Vertical Cuts: For every possible vertical cut j from 1 to w-1, split the rectangle into (h x j) and (h x (w-j)), recursively compute revenues, and update the maximum revenue.
  7. Memoize and Return: Store the computed maximum revenue in dp[(h, w)] and return it.
  8. Final Call: Start by calling dfs(m, n) to compute the maximum revenue for the original piece of wood.

Why it works: The recursion guarantees that all possible cutting combinations are considered. Memoization ensures each subrectangle is only solved once, providing an efficient solution. Since the price for a rectangle depends solely on its dimensions, the subproblem decomposition satisfies optimal substructure.

Python Solution

from typing import List, Tuple
from functools import lru_cache

class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        price_map = {(h, w): price for h, w, price in prices}

        from functools import lru_cache

        @lru_cache(None)
        def dfs(h: int, w: int) -> int:
            max_val = price_map.get((h, w), 0)
            
            # Try horizontal cuts
            for i in range(1, h):
                max_val = max(max_val, dfs(i, w) + dfs(h - i, w))
            
            # Try vertical cuts
            for j in range(1, w):
                max_val = max(max_val, dfs(h, j) + dfs(h, w - j))
            
            return max_val

        return dfs(m, n)

Explanation: We first map the prices for O(1) access. The dfs function recursively explores all cutting options for a rectangle. The use of lru_cache implements memoization, preventing recomputation of subrectangles. The function returns the maximum possible revenue for the requested dimensions.

Go Solution

func sellingWood(m int, n int, prices [][]int) int64 {
    priceMap := make(map[[2]int]int64)
    for _, p := range prices {
        priceMap[[2]int{p[0], p[1]}] = int64(p[2])
    }

    memo := make(map[[2]int]int64)

    var dfs func(h, w int) int64
    dfs = func(h, w int) int64 {
        key := [2]int{h, w}
        if val, ok := memo[key]; ok {
            return val
        }
        maxVal := priceMap[key]

        for i := 1; i < h; i++ {
            maxVal = max(maxVal, dfs(i, w)+dfs(h-i, w))
        }
        for j := 1; j < w; j++ {
            maxVal = max(maxVal, dfs(h, j)+dfs(h, w-j))
        }

        memo[key] = maxVal
        return maxVal
    }

    var max func(a, b int64) int64
    max = func(a, b int64) int64 {
        if a > b {
            return a
        }
        return b
    }

    return dfs(m, n)
}

Go-specific Notes: We use a map with array keys [2]int to represent rectangle dimensions. All integers are cast to int64 to avoid overflow. Memoization is implemented explicitly with the memo map.

Worked Examples

Example 1: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]

Step Operation Revenue Calculation Max Revenue
Initial No cuts max(0, prices.get(3,5)=0) 0
Horizontal cut at 2 Split 2x5 + 1x5 dfs(2,5)+dfs(1,5) 19
Vertical cut at 2 Split 3x2 + 3x3 dfs(3,2)+dfs(3,3) 18
Horizontal cut at 1 Split 1x5 + 2x5 dfs(1,5)+dfs(2,5) 19
Vertical cut at 4 Split 3x4 + 3x1 dfs(3,4)+dfs(3,1) 18

Maximum revenue returned: 19

Example 2: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]

Following similar splitting steps, the maximum revenue obtained is 32.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * (m + n)) Each subrectangle is computed once. For each subrectangle, we try at most h-1 horizontal and w-1 vertical cuts.
Space O(m * n + p) Memoization table stores results for each subrectangle, plus a map of prices with p entries.

The reasoning: memoization ensures each (h, w) is solved only once, and trying all cuts takes linear time in height and width.

Test Cases

# Provided examples
assert Solution().sellingWood(3, 5, [[1,4,2],[2,2,7],[2,1,3]]) == 19  # Example 1
assert Solution().sellingWood(4, 6, [[3,2,10],[1,4,