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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Selling Pieces of Wood

Difficulty: Hard

Problem Description

You are given two integers m and n that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array prices, where prices[i] = [h_i, w_i, price_i] indicates you can sell a rectangular piece of wood of height h_i and width w_i for price_i dollars. To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to prices. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width. Return the maximum money you can earn after cutting an m x n piece of wood. Note that you can cut the piece of wood as many times as you want.

Key Insights

  • The problem requires maximizing profit from selling wood pieces with given dimensions and prices.
  • Cuts can be made vertically or horizontally, allowing for multiple smaller pieces to be sold.
  • A dynamic programming approach can be utilized to keep track of maximum profits for each sub-dimension of the wood piece.
  • The problem has a recursive nature where the solution for larger dimensions can be built from smaller dimensions.

Space and Time Complexity

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

Solution

The solution involves using a dynamic programming approach where we create a 2D array dp where dp[i][j] represents the maximum profit that can be obtained from a wood piece of dimensions i x j. We initialize the dp array based on the prices available for specific dimensions directly. Then, for each dimension, we explore all possible vertical and horizontal cuts, calculating the maximum profit possible from the resulting pieces. The final answer will be stored in dp[m][n], which will represent the maximum profit for the piece of wood of size m x n.

Code Solutions

def sellingWood(m, n, prices):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for h, w, price in prices:
        dp[h][w] = max(dp[h][w], price)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            for cut in range(1, i // 2 + 1):
                dp[i][j] = max(dp[i][j], dp[cut][j] + dp[i - cut][j])
            for cut in range(1, j // 2 + 1):
                dp[i][j] = max(dp[i][j], dp[i][cut] + dp[i][j - cut])
    
    return dp[m][n]
← Back to All Questions