class Solution {
public:
int pileBox(vector<vector<int>>& box) {
}
};
面试题 08.13. 堆箱子
堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。
示例1:
输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] 输出：6
示例2:
输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] 输出：10
提示:
原站题解
python3 解法, 执行用时: 468 ms, 内存消耗: 16.4 MB, 提交时间: 2023-04-22 11:32:41
class Solution:
def pileBox(self, box: List[List[int]]) -> int:
@functools.lru_cache(3000)
def dfs(w, d, h):
valid = [(wi, di, hi) for wi, di, hi in box if wi < w and di < d and hi < h]
if not valid:
return h
return max(dfs(wi, di, hi) for wi, di, hi in valid) + h
return max(dfs(w, d, h) for w, d, h in box)
python3 解法, 执行用时: 4748 ms, 内存消耗: 16.1 MB, 提交时间: 2023-04-22 11:32:21
class Solution:
def pileBox(self, box: List[List[int]]) -> int:
n = len(box)
dp = [0] * n
box.sort(key=lambda x:(x[0],-x[1]))
for i in range(n):
dp[i] = box[i][2]
for j in range(i):
if all(box[j][k] < box[i][k] for k in range(1,3)):
dp[i] = max(dp[i], dp[j] + box[i][2])
return max(dp)
cpp 解法, 执行用时: 140 ms, 内存消耗: 8.8 MB, 提交时间: 2023-04-22 11:31:50
class Solution {
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<int> dp(box.size(), 0);
dp[0] = box[0][2];
int ans = dp[0];
for (int i = 1; i < box.size(); i++) {
int maxh = 0; //必须初始化为0
for (int j = 0; j < i; j++)
if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2])
maxh = max(maxh, dp[j]);
dp[i] = maxh + box[i][2];
ans = max(ans, dp[i]);
}
return ans;
}
};
java 解法, 执行用时: 39 ms, 内存消耗: 40.8 MB, 提交时间: 2023-04-22 11:31:11
/**
思路：每个箱子有三个维度，按照宽进行排序后降为二维，即可用最长上升子序列的思路来解。
状态方程：
dp[i] 表示以第 i 个箱子为最底端箱子时，箱堆的最大高度。
dp[i] = Max( dp[j] ) + box[i][2] 其中 0 <= j < i ,且 i 的三维都要比 j 大
*/
class Solution {
public int pileBox(int[][] box) {
Arrays.sort(box, (x, y) -> x[0] - y[0]);
int[] dp = new int[box.length];
int res = 0;
for(int i = 0; i < box.length; ++i){
for(int j = 0; j < i; ++j){
// i 的三维都要比 j 大
if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]){
//在 0 <= j < i 范围内找到最大的 dp[j]
dp[i] = Math.max(dp[i], dp[j]);
}
}
//最后加上最底端箱子的高度
dp[i] += box[i][2];
res = Math.max(dp[i], res);
}
return res;
}
}