Leetcode Problem 2312. Selling Pieces of Wood

2312. Selling Pieces of Wood

Leetcode Solutions

Dynamic Programming - Bottom-Up Approach

  1. Initialize a 2D DP array dp with dimensions (m+1) x (n+1) and set all values to 0.
  2. Populate the DP array with the given prices for specific pieces of wood.
  3. Iterate over all possible heights i from 1 to m.
  4. Iterate over all possible widths j from 1 to n.
  5. For each cell dp[i][j], consider all possible horizontal cuts at height h from 1 to i/2 and update dp[i][j] to the maximum of its current value or the sum of dp[h][j] and dp[i-h][j].
  6. Consider all possible vertical cuts at width w from 1 to j/2 and update dp[i][j] to the maximum of its current value or the sum of dp[i][w] and dp[i][j-w].
  7. After filling the DP array, return the value at dp[m][n] as the final answer.
UML Thumbnail

D Dynamic Programming - Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...