Problem statement

You have a rectangular piece of wood of height m and width n. You are also given prices, where prices[i] = [hi, wi, pricei] means a piece of height hi and width wi sells for pricei dollars.

To cut a piece, make one straight cut across its entire height or entire width, splitting it into two smaller pieces. You may cut as many times as you like, then sell any of the resulting pieces whose exact shape appears in prices (as many pieces of a shape as you have). Pieces with no listed shape earn nothing. The grain of the wood matters, so a piece can not be rotated: an h x w piece only matches [h, w, …].

Return the maximum amount of money you can earn from the m x n piece. (On CodeKairo the prices are capped at 10^4 so the answer fits in a 32-bit integer.)

Example 1

Input: m = 2, n = 3, prices = [[1,1,2],[2,3,10],[1,3,7]]
Output: 14
Explanation: Cut the board into two `1 x 3` strips and sell both for 7.

Example 2

Input: m = 3, n = 3, prices = [[2,2,9],[1,1,1]]
Output: 14
Explanation: One `2 x 2` piece for 9 and the five remaining `1 x 1` squares for 1 each.

Example 3

Input: m = 1, n = 4, prices = [[1,2,3],[1,3,5]]
Output: 6
Explanation: Two `1 x 2` pieces (3 + 3) beat a `1 x 3` piece plus an unsellable `1 x 1` (5).

Constraints

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 10^4
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 10^4
• all shapes (hi, wi) are pairwise distinct

Hints for Selling Pieces of Wood

1. Hint 1

   Every cut runs all the way across, so after any number of cuts each piece is again a full rectangle — described only by its height and width.

2. Hint 2

   Let best[h][w] be the most an h x w piece can earn. Either sell it whole (its listed price, or 0), or make the first cut and solve both halves independently.

3. Hint 3

   best[h][w] = max(price[h][w], best[i][w] + best[h-i][w] for 1 <= i < h, best[h][j] + best[h][w-j] for 1 <= j < w). Fill the table by increasing size; checking only i <= h / 2 and j <= w / 2 is enough by symmetry.

How to solve Selling Pieces of Wood

Full-length cuts keep every piece a rectangle, and the two pieces of a cut are processed independently afterwards. So the value of a piece depends only on its dimensions: a 2-D DP over (height, width) with one 'first cut' choice per state.

Approach

1. Build price[h][w] from the list (0 for unlisted shapes).
2. For h from 1 to m and w from 1 to n: start with best[h][w] = price[h][w].
3. Try every horizontal first cut i from 1 to h / 2: best[i][w] + best[h-i][w].
4. Try every vertical first cut j from 1 to w / 2: best[h][j] + best[h][w-j].
5. Keep the maximum and return best[m][n].

Why it works

Any selling plan either sells the whole piece or begins with some full cut; after that cut the two parts are disjoint rectangles whose plans do not interact, so the best plan for each is the DP value of its shape. Both pieces are strictly smaller, so filling by increasing height and width has them ready. A cut at i and at h - i give the same two shapes, which is why half the positions suffice.

Complexity

• Time — O(m · n · (m + n))
• Space — O(m · n)

Pitfalls

• Pieces cannot be rotated: [2,1,…] and [1,2,…] are different shapes.
• Selling a piece whole is optional — a listed price can be beaten by cutting it further.
• On LeetCode prices reach 10^6 and the answer needs 64 bits; here prices are capped at 10^4 so it fits in 32.

Reference solution

Python

from typing import List

def sellingWood(m: int, n: int, prices: List[List[int]]) -> int:
    best = [[0] * (n + 1) for _ in range(m + 1)]
    for h, w, p in prices:
        best[h][w] = max(best[h][w], p)
    for h in range(1, m + 1):
        for w in range(1, n + 1):
            top = best[h][w]
            for i in range(1, h // 2 + 1):
                v = best[i][w] + best[h - i][w]
                if v > top:
                    top = v
            for j in range(1, w // 2 + 1):
                v = best[h][j] + best[h][w - j]
                if v > top:
                    top = v
            best[h][w] = top
    return best[m][n]

Java

public static int sellingWood(int m, int n, int[][] prices) {
    long[][] best = new long[m + 1][n + 1];
    for (int[] p : prices) best[p[0]][p[1]] = Math.max(best[p[0]][p[1]], p[2]);
    for (int h = 1; h <= m; h++) {
        for (int w = 1; w <= n; w++) {
            long top = best[h][w];
            for (int i = 1; i * 2 <= h; i++) top = Math.max(top, best[i][w] + best[h - i][w]);
            for (int j = 1; j * 2 <= w; j++) top = Math.max(top, best[h][j] + best[h][w - j]);
            best[h][w] = top;
        }
    }
    return (int) best[m][n];
}

C++

int sellingWood(int m, int n, vector<vector<int>>& prices) {
    vector<vector<long long>> best(m + 1, vector<long long>(n + 1, 0));
    for (auto& p : prices) best[p[0]][p[1]] = max(best[p[0]][p[1]], (long long)p[2]);
    for (int h = 1; h <= m; h++) {
        for (int w = 1; w <= n; w++) {
            long long top = best[h][w];
            for (int i = 1; i * 2 <= h; i++) top = max(top, best[i][w] + best[h - i][w]);
            for (int j = 1; j * 2 <= w; j++) top = max(top, best[h][j] + best[h][w - j]);
            best[h][w] = top;
        }
    }
    return (int)best[m][n];
}

JavaScript

var sellingWood = function(m, n, prices) {
    var best = [];
    for (var h = 0; h <= m; h++) best.push(new Array(n + 1).fill(0));
    for (var t = 0; t < prices.length; t++) {
        var p = prices[t];
        best[p[0]][p[1]] = Math.max(best[p[0]][p[1]], p[2]);
    }
    for (var h = 1; h <= m; h++) {
        for (var w = 1; w <= n; w++) {
            var top = best[h][w];
            for (var i = 1; i * 2 <= h; i++) top = Math.max(top, best[i][w] + best[h - i][w]);
            for (var j = 1; j * 2 <= w; j++) top = Math.max(top, best[h][j] + best[h][w - j]);
            best[h][w] = top;
        }
    }
    return best[m][n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard