We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Selling Pieces of Wood

Number: 1376

Difficulty: Hard

Paid? No

Companies: Palantir Technologies

Problem Description

Given an m x n piece of wood and a list of available sellable pieces (each specified by height, width, and price), determine the maximum revenue obtainable by cutting the wood. You may cut the wood by making vertical or horizontal cuts across the entire piece, and you may sell any resulting piece if it exactly matches one of the provided dimensions (rotations are not allowed).

Key Insights

  • Use dynamic programming to solve for maximum revenue for every sub-piece of wood.
  • For every dimension (i x j), consider selling it directly if there is a price, or try every possible vertical and horizontal cut.
  • The recurrence: dp[i][j] is the max between selling the piece directly (if available) and splitting it into two pieces, summing the best revenues obtainable from the split parts.
  • Bottom-up DP is efficient since m and n are small (each up to 200), and we have to check cuts over all possible splits.

Space and Time Complexity

Time Complexity: O(m * n * (m + n))
Space Complexity: O(m * n)

Solution

We solve the problem with a bottom-up dynamic programming approach. We use a 2D dp array where dp[i][j] captures the maximum revenue obtainable from a wood piece of dimensions i x j. We initialize dp[i][j] with a direct sale price if the piece exactly matches one of the provided sizes; otherwise, it starts at zero. Then, for each dimension we iterate over all possible vertical and horizontal cuts to update dp[i][j] with the maximum revenue obtainable from any such split. This approach systematically builds up the answer from the smallest pieces to the full m x n piece.

Code Solutions

# Python solution using bottom-up dynamic programming

def sellingWood(m, n, prices):
    # Create a price dictionary for quick lookup
    price_dict = {(h, w): price for h, w, price in prices}
    
    # dp[i][j] is maximum revenue from a piece of wood of height i and width j
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build dp in increasing order of dimensions
    for height in range(1, m + 1):
        for width in range(1, n + 1):
            # If current dimension can be directly sold, take that price
            if (height, width) in price_dict:
                dp[height][width] = price_dict[(height, width)]
            # Try all vertical cuts: cut horizontally into two parts
            for cut in range(1, height):
                dp[height][width] = max(dp[height][width], dp[cut][width] + dp[height - cut][width])
            # Try all horizontal cuts: cut vertically into two parts
            for cut in range(1, width):
                dp[height][width] = max(dp[height][width], dp[height][cut] + dp[height][width - cut])
    return dp[m][n]

# Example usage:
# m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
#print(sellingWood(3, 5, [[1,4,2],[2,2,7],[2,1,3]]))  # Output: 19
← Back to All Questions