以百度云做网站空间互联网金融

题目链接

堆箱子

题目描述

注意点

• 将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子

解答思路

• 初始想到深度优先遍历，最后超时了
• 参照题解使用动态规划，先将盒子从小到大进行排序，dp[i]存储的是到第i个箱子时堆箱子的最大高度，初始只取一个箱子计算dp[0]，然后取两个箱子计算dp[1]…以此类推，计算出dp[n]的值
• 怎样计算dp[i]的值：已经知道dp[0]到dp[i - 1]的值，根据第i个箱子是否能堆到第j个箱子下，找到能堆到第j个箱子的前提下dp[j]的最大值，dp[i] = Math.max(dp[j]) + box[i][2]

代码

class Solution {public int pileBox(int[][] box) {int res = 0;int n = box.length;Arrays.sort(box, new Comparator<int[]>() {public int compare(int[] box1, int[] box2) {if (box1[0] != box2[0]) {return box1[0] - box2[0];}if (box1[1] != box2[1]) {return box1[1] - box2[1];}return box1[2] - box2[2];}});// dp[i]表示直到第i个箱子的最大高度int[] dp = new int[n];// 第一个循环寻找从第0个箱子到第n个箱子堆箱子组合的最大高度dp[i]for (int i = 0; i < n; i++) {// 第二个循环寻找第i个箱子能堆在下面的前提下，前面所堆的箱子组合的最大高度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]) {dp[i] = Math.max(dp[i], dp[j]);}}// 前面的箱子组合还要加上第i个箱子dp[i] += box[i][2];res = Math.max(res, dp[i]);}return res;}
}

关键点

• 动态规划的思想