Selling pieces of wood

Array Dynamic Programming Memoization

52.7% acceptance

Feb 25, 2026

578

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] = [hi, wi, pricei]. To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width. Return the maximum money you can earn after cutting an m x n piece of wood.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn selling_wood(m: i32, n: i32, prices: Vec<Vec<i32>>) -> i64 {
    let (m, n) = (m as usize, n as usize);
    let mut dp = vec![vec![0i64; n + 1]; m + 1];
    for p in &prices {
      dp[p[0] as usize][p[1] as usize] = p[2] as i64;
    }
    for h in 1..=m {
      for w in 1..=n {
        for hcut in 1..h {
          let val = dp[hcut][w] + dp[h - hcut][w];
          if val > dp[h][w] {
            dp[h][w] = val;
          }
        }
        for wcut in 1..w {
          let val = dp[h][wcut] + dp[h][w - wcut];
          if val > dp[h][w] {
            dp[h][w] = val;
          }
        }
      }
    }
    dp[m][n]
  }
}