題目：堆箱子
輸入使用數組[wi, di, hi]表示每個箱子。
示例1：
輸入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]輸出：6
輸入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]輸出：10
箱子的數目不大于3000個。
分析
這題在回溯類型下，但無奈用回溯方法會超時，剪枝太麻煩，就使用了動態規劃方法，首先選擇 一個維度對輸入box排序，用dp保存當前節點在底部的最大高度，見代碼
代碼
class Solution {public:int pileBox(vector<vector<int>>& box) {// 首先對輸入box選擇一個維度排序std::sort(box.begin(), box.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];});int size = box.size();vector<int> dp(size, 0); // dp保存當前節點在底部的最大高度dp[0] = box[0][2];int ret = dp[0];for (int i = 1; i < size; ++i) {int max_val = 0;for (int j = 0; j < i; ++j) {if (IsValid(box[j], box[i])) {max_val = max(max_val, dp[j]);}}dp[i] = max_val + box[i][2];ret = max(ret, dp[i]);}return ret;}bool IsValid(vector<int> &up, vector<int> &down) {return (down.at(0) > up.at(0)&& down.at(1) > up.at(1)&& down.at(2) > up.at(2));}};