Selling Pieces of Wood - Practice Coding Problems

Selling Pieces of Wood - Problem

Imagine you're a master woodworker who has just acquired a beautiful rectangular piece of wood with dimensions m × n. You have access to a price catalog that tells you exactly how much you can sell different rectangular pieces for.

Your goal is to maximize your profit by strategically cutting the wood and selling the pieces. You can make:

Vertical cuts - slice through the entire height
Horizontal cuts - slice through the entire width

The wood grain matters, so you cannot rotate pieces (height and width are fixed). You're given a 2D array prices where prices[i] = [hi, wi, pricei] means a piece of height hi and width wi sells for pricei dollars.

Key considerations:

You can cut as many times as you want
You can sell multiple pieces of the same dimensions
You don't have to sell every piece you cut
Some cuts might result in more valuable smaller pieces

Return the maximum money you can earn from your m × n piece of wood.

Input & Output

example_1.py — Basic Wood Cutting

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

› Output: 19

💡 Note: The optimal strategy is to make a horizontal cut at position 2, creating two pieces: one 2×5 piece and one 1×5 piece. The 2×5 piece can be cut vertically into five 2×1 pieces (each worth 3), and the 1×5 piece can be cut vertically into one 1×4 piece (worth 2) and one 1×1 piece (unsold). Total: 5×3 + 2 + 0 = 17. Wait, let me recalculate: we can get two 2×2 pieces (7 each) and one 2×1 piece (3), plus one 1×4 piece (2) and one 1×1 piece. So 7+7+3+2 = 19.

example_2.py — No Cuts Needed

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

› Output: 32

💡 Note: We can make vertical cuts to get six 4×1 pieces, each worth 3. Total profit = 6 × 3 = 18. Alternatively, we can make horizontal cuts and vertical cuts to get other combinations, but the optimal turns out to be different cuts yielding 32.

example_3.py — Edge Case - Single Cell

$ Input: m = 1, n = 1, prices = [[1,1,5]]

› Output: 5

💡 Note: The wood is already 1×1 and matches exactly one price entry. We sell it directly for 5 dollars without any cuts.

Constraints

1 ≤ m, n ≤ 200
1 ≤ prices.length ≤ 2 × 10⁴
prices[i].length == 3
1 ≤ hi ≤ m
1 ≤ wi ≤ n
1 ≤ pricei ≤ 10⁶
Multiple entries may have the same dimensions - take the maximum price

Visualization

Tap to expand

Understanding the Visualization

Price Catalog Setup

Create a lookup table for all available piece prices, keeping the maximum price for duplicate dimensions

Recursive Exploration

For each piece, consider selling directly or making cuts. Try all possible horizontal and vertical cut positions

Memoization Magic

Store results for each piece size to avoid recalculating the same subproblems multiple times

Optimal Solution

Build up from smaller pieces to larger ones, always choosing the option that yields maximum profit

Key Takeaway

🎯 Key Insight: Memoization transforms an exponential brute force solution into an efficient polynomial-time algorithm by avoiding redundant calculations of the same subproblems.

Asked in

G Google 42 a Amazon 38 f Meta 29 ⊞ Microsoft 24

This wood cutting problem is solved optimally using dynamic programming with memoization. The key insight is that the optimal way to cut any piece depends on the optimal solutions for all smaller pieces. By storing results of subproblems, we avoid exponential recalculation and achieve O(m²n + mn²) time complexity. Each piece size is computed once, and we try all possible cuts to find the maximum profit.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization (Optimal)	O(m²n + mn²)	O(mn)	Add memoization to avoid recalculating the same subproblems
Brute Force Recursion	O(2^(m*n))	O(m*n)	Try all possible cuts recursively without memoization

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Create a memoization table (2D array or hash map)
For each piece, check if we've already solved it
If yes, return the cached result immediately
If no, calculate using recursion and store the result
Try all possible cuts and return the maximum profit

Visualization

Tap to expand

Step-by-Step Walkthrough

First Calculation

Calculate solve(2,3) and store result in memo table

Cache Hit

When solve(2,3) is needed again, return cached result immediately

Build Up Solutions

Use smaller solutions to build larger ones efficiently

Optimal Result

Each subproblem solved exactly once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int h, w;
    long long price;
} PriceEntry;

typedef struct {
    int h, w;
    long long result;
} MemoEntry;

PriceEntry prices[1000];
MemoEntry memo[201][201];
int priceCount = 0;
int memoInitialized = 0;

void initMemo() {
    if (memoInitialized) return;
    for (int i = 0; i <= 200; i++) {
        for (int j = 0; j <= 200; j++) {
            memo[i][j].result = -1;
        }
    }
    memoInitialized = 1;
}

long long findPrice(int h, int w) {
    long long maxPrice = 0;
    for (int i = 0; i < priceCount; i++) {
        if (prices[i].h == h && prices[i].w == w) {
            if (prices[i].price > maxPrice) {
                maxPrice = prices[i].price;
            }
        }
    }
    return maxPrice;
}

long long solve(int h, int w) {
    if (h <= 0 || w <= 0) return 0;
    if (h <= 200 && w <= 200 && memo[h][w].result != -1) {
        return memo[h][w].result;
    }
    
    long long maxProfit = findPrice(h, w);
    
    // Try horizontal cuts
    for (int cut = 1; cut < h; cut++) {
        long long top = solve(cut, w);
        long long bottom = solve(h - cut, w);
        if (top + bottom > maxProfit) {
            maxProfit = top + bottom;
        }
    }
    
    // Try vertical cuts
    for (int cut = 1; cut < w; cut++) {
        long long left = solve(h, cut);
        long long right = solve(h, w - cut);
        if (left + right > maxProfit) {
            maxProfit = left + right;
        }
    }
    
    if (h <= 200 && w <= 200) {
        memo[h][w].result = maxProfit;
    }
    return maxProfit;
}

int main() {
    initMemo();
    int m, n;
    scanf("%d %d", &m, &n);
    
    int h, w, p;
    while (scanf("%d %d %d", &h, &w, &p) == 3) {
        prices[priceCount].h = h;
        prices[priceCount].w = w;
        prices[priceCount].price = p;
        priceCount++;
    }
    
    printf("%lld\n", solve(m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n + mn²)

Each of the mn subproblems tries O(m+n) cuts, and each subproblem is solved only once

⚠ Quadratic Growth

Space Complexity

O(mn)

Memoization table stores results for each possible piece size plus recursion stack

⚡ Linearithmic Space

78.0K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler