Maximum Height by Stacking Cuboids

给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度.

这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp.

设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.

public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;
        int[] dp = new int[n];
        int res = 0;
        for(int[] c : cuboids){
            Arrays.sort(c);
        }
        Arrays.sort(cuboids,(a,b) -> a[2] != b[2] ? b[2] - a[2] : a[1] != b[1] ? b[1] - a[1] : a[0] != b[0] ? b[0] - a[0]: 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++){
                if(cuboids[i][0] <= cuboids[j][0] && cuboids[i][1] <= cuboids[j][1] && cuboids[i][2] <= cuboids[j][2]) {
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            dp[i] += cuboids[i][2];
            res = Math.max(res, dp[i]);
        }
        return res;
    }