selling-pieces-of-wood

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two integers <code>m</code> and <code>n</code> that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array <code>prices</code>, where <code>prices[i] = [hi, wi, pricei]</code> indicates you can sell a rectangular piece of wood of height <code>hi</code> and width <code>wi</code> for <code>pricei</code> 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 <code>prices</code>. 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 <code>m x n</code> piece of wood.

Note that you can cut the piece of wood as many times as you want.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/04/27/ex1.png" style="width: 239px; height: 150px;" />
<pre>
Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
Output: 19
Explanation: The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/04/27/ex2new.png" style="width: 250px; height: 175px;" />
<pre>
Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
Output: 32
Explanation: The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>1 &lt;= prices.length &lt;= 2 * 104</code></li>
	<li><code>prices[i].length == 3</code></li>
	<li><code>1 &lt;= hi &lt;= m</code></li>
	<li><code>1 &lt;= wi &lt;= n</code></li>
	<li><code>1 &lt;= pricei &lt;= 106</code></li>
	<li>All the shapes of wood <code>(hi, wi)</code> are pairwise distinct.</li>
</ul>

sellingWood

Selling Pieces of Wood

Tiling a Rectangle with the Fewest Squares

tiling-a-rectangle-with-the-fewest-squares

铺瓷砖

Number of Ways of Cutting a Pizza

number-of-ways-of-cutting-a-pizza

切披萨的方案数

Memoization

Array

Dynamic Programming

给你两个整数&nbsp;<code>m</code> 和&nbsp;<code>n</code>&nbsp;，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组&nbsp;<code>prices</code>&nbsp;，其中&nbsp;<code>prices[i] = [hi, wi, pricei]</code>&nbsp;表示你可以以&nbsp;<code>pricei</code>&nbsp;元的价格卖一块高为&nbsp;<code>hi</code>&nbsp;宽为&nbsp;<code>wi</code>&nbsp;的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

<ul>
	<li>沿垂直方向按高度 完全 切割木块，或</li>
	<li>沿水平方向按宽度 完全 切割木块</li>
</ul>

在将一块木块切成若干小木块后，你可以根据 <code>prices</code>&nbsp;卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能&nbsp;旋转切好后木块来交换它的高度值和宽度值。

请你返回切割一块大小为&nbsp;<code>m x n</code> 的木块后，能得到的&nbsp;最多&nbsp;钱数。

注意你可以切割木块任意次。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/04/27/ex1.png" style="width: 239px; height: 150px;" />

<pre>
输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/04/27/ex2new.png" style="width: 250px; height: 175px;" />

<pre>
输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>1 &lt;= prices.length &lt;= 2 * 104</code></li>
	<li><code>prices[i].length == 3</code></li>
	<li><code>1 &lt;= hi &lt;= m</code></li>
	<li><code>1 &lt;= wi &lt;= n</code></li>
	<li><code>1 &lt;= pricei &lt;= 106</code></li>
	<li>所有&nbsp;<code>(hi, wi)</code> 互不相同&nbsp;。</li>
</ul>