O(n^2)算法
将箱子按照任意维度进行排序，那么答案毫无疑问就是子序列(排序是为了保证出现在后面的箱子不可能具有堆在前面的箱子下面的可能性，维持有序才有子序列)
对于每一个箱子来说，以他为顶的最高高度是在子序列之前所有符合条件的箱子堆出来的堆中最高的加上他自己的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int pileBox(vector<vector<int>>& box) {
sort(box.begin(), box.end(), [](vector<int>& b1, vector<int>& b2){ return b1[2] < b2[2]; });
vector<int> dp(box.size(), 0);
dp[0] = box[0][2];
int ret = 0;
for(int i = 1; i < box.size(); ++i)
{
dp[i] = box[i][2];
for(int j = 0; j < i; ++j)
if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2])
dp[i] = max(dp[i], dp[j] + box[i][2]);
ret = max(ret, dp[i]);
}
return ret;
}
};
|