面试题 08.13. 堆箱子

题目要求处于下方的箱子是严格大于上面的箱子的，所以只需要对其中一个参数进行排序后得到的数组，答案必定是该数组中的一个子序列，即最长上升子序列问题（升序排就是上升，降序排就是下降子序列），接着就是动态规划的思想，dp[i]表示以箱子i为底的最大高度为多少，因此对于每一个箱子box[i] ，我们只需要关注该箱子的上面一个是哪个就可以了，即dp[i] = MAX(dp[i], dp[j] + box[i][2])，

class Solution {
    public int pileBox(int[][] box) {
        Arrays.sort(box, (o1, o2) -> o1[0] - o2[0]);
        int[] dp = new int[box.length];
        int ans = 0;
        for(int i = 0; i < box.length; i++){
            dp[i] += box[i][2];
            for(int j = 0; j < i; j++){
                if(box[i][1] > box[j][1] && box[i][2] > box[j][2] && box[i][0] > box[j][0])
                    dp[i] = Math.max(dp[i],box[i][2] + dp[j]);
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16