Daily LeetCode – day0134 1691. Maximum Height by Stacking Cuboids

import java.util.Arrays;

// 1691. Maximum Height by Stacking Cuboids
class Solution {
    public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;
        for (int[] cuboid : cuboids) Arrays.sort(cuboid);
        Arrays.sort(cuboids, (c1, c2) -> (c1[0] + c1[1] + c1[2]) - (c2[0] + c2[1] + c2[2]));
        int ans = 0;
        int[] maxHeights = new int[n];
        for (int i = 0; i < n; ++i) {
            maxHeights[i] = cuboids[i][2];
            ans = Math.max(ans, maxHeights[i]);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (cuboids[j][0] <= cuboids[i][0] && cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
                    maxHeights[i] = Math.max(maxHeights[i], maxHeights[j] + cuboids[i][2]);
                }
            }
            ans = Math.max(ans, maxHeights[i]);
        }
        return ans;
    }
}

学习笔记：
好家伙，两天简单题，之后直接今天来了一道困难题。
这是一道动态规划、排序的题目。
先要根据数学的理论一通推理，最优方案一定是把每个盒子最长边放在高上。
先把cuboids每个盒子内部排序，从短到长。
然后再整体排序，总长从短到长。
然后每一个盒子的状态转移方程式就是要找能放在他上面的最大的盒子高度。