卖木头块(Lc2312)——动态规划

本文主要是介绍卖木头块(Lc2312)——动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

• 沿垂直方向按高度 完全 切割木块，或
• 沿水平方向按宽度 完全 切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。

请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。

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

示例 1：

输入：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 元是最多能得到的钱数。

示例 2：

输入：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 的木块。

提示：

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 104
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 106
• 所有 (hi, wi) 互不相同 。

问题简要描述：返回能得到的最多钱数 

细节阐述:

1.  d[i][j] 表示高为 i，宽为 j 的木块的价格，f[i][j] 表示一块高为 i，宽为 j 的木块切割后能得到的最多钱数

Java

class Solution {public long sellingWood(int m, int n, int[][] prices) {int[][] d = new int[m + 1][n + 1];long[][] f = new long[m + 1][n + 1];for (int[] p : prices) {d[p[0]][p[1]] = p[2];}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {f[i][j] = d[i][j];for (int k = 1; k < i; k++) {f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);}for (int k = 1; k < j; k++) {f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);}}}return f[m][n];}
}

 Python3

class Solution:def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:d = defaultdict(dict)for h, w, p in prices:d[h][w] = pf = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):f[i][j] = d[i].get(j, 0)for k in range(1, i):f[i][j] = max(f[i][j], f[k][j] + f[i - k][j])for k in range(1, j):f[i][j] = max(f[i][j], f[i][k] + f[i][j - k])return f[m][n]     

TypeScript

function sellingWood(m: number, n: number, prices: number[][]): number {let d = Array.from({length: m + 1}, () => Array(n + 1).fill(0));let f = Array.from({length: m + 1}, () => Array(n + 1).fill(0));for (const [h, w, p] of prices) {d[h][w] = p;}for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {f[i][j] = d[i][j];for (let k = 1; k < i; k++) {f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);}for (let k = 1; k < j; k++) {f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);}}}return f[m][n];  
};

这篇关于卖木头块(Lc2312)——动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---