#### link：https://leetcode.com/problems/maximum-height-by-stacking-cuboids/description/

* 學習找「狀態」
* 通過思考，建一個 dp 表，dp[i] 指的是以第 i 個元素作為底的最大高度
* 因此，我們要先 sort 方塊的長寬高，並且從最小的高度開始看起 => base case ( 這題能這樣做是因為題目限定了上面方塊的長寬高都要比下面的小，所以我們只要把最長的當作高就行了 )
* 基本上經過 sort 之後第一個 ( 或最後一個，看你是升序排列還是降序排列 ) 會是最小的，用那個當 base case，一路往大的方塊漸漸尋訪。( 如果從最大的方塊開始會出問題，這裡我卡了很久 )

class Solution {
public:
    static bool cmp(int a, int b){
        return a > b;
    }
    static bool cmp1(vector<int> &a, vector<int> &b){
        if (a[0] != b[0]) return a[0] > b[0];
        else if (a[1] != b[1] ) return a[1] > b[1] ;
        else return a[2] > b[2];
    }

    bool compare(int k, int r, vector<vector<int>> &cuboids, vector<int> &dp){
        return (cuboids[r][0] >= cuboids[k][0] && cuboids[r][1] >= cuboids[k][1] && cuboids[r][2] >= cuboids[k][2]);
    }

    int maxHeight(vector<vector<int>>& cuboids) {
        int n = cuboids.size();
        for (int i = 0; i < n; i++){
            sort(cuboids[i].begin(), cuboids[i].end(), &Solution::cmp);
        }
        sort(cuboids.begin(), cuboids.end(), &Solution::cmp1);
        for (int i = 0; i < n; i++){
            int k = 0;
            for (int j = 0; j < 3; j++, k++){
                cout << cuboids[i][j]<<" ";
            }
            cout << endl;
        }

        int m = cuboids[n - 1][0];;
        vector<int> dp(n, 0);
    
        for (int i = n - 1; i >= 0; i--){
            dp[i] = cuboids[i][0];
            for (int j = i+1; j < n; j++){
                if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2] ){
                    dp[i] = max(dp[j] + cuboids[i][0], dp[i]);
                    
                }
                m = max(dp[i], m);
            }
        }

        return m;
    }
};