C++刷LeetCode（面试题 08.13. 堆箱子）【动态规划】*

糖逗

题目描述：

1. 堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
   
2. 
   
3. 输入使用数组[wi, di, hi]表示每个箱子。
   
4. 
   
5. 示例1:
   
6. 
   
7. 输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
   
8. 输出：6
   
9. 示例2:
   
10. 
    
11. 输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
    
12. 输出：10
    
13. 提示:
    
14. 
    
15. 箱子的数目不大于3000个。
    
16. 
    
17. 来源：力扣（LeetCode）
    
18. 链接：https://leetcode.cn/problems/pile-box-lcci
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int pileBox(vector<vector<int>>& box) {
   
4.         int n = box.size();
   
5.         sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b){
   
6.             return a[0] < b[0];
   
7.         });
   
8.         //初始化
   
9.         vector<int>dp(n, 0);
   
10.         dp[0] = box[0][2];
    
11.         int res = dp[0];
    
12.         //动态规划dp[i]表示最后一个为i的maxhi
    
13.         for(int i = 1; i < n; i++){
    
14.             dp[i] = box[i][2];//初始至少为自己的高度
    
15.             for(int j = 0; j < i; j++){
    
16.                 if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]){
    
17.                     dp[i] = max(dp[i], dp[j] + box[i][2]);
    
18.                 }
    
19.             }
    
20.             res = max(res, dp[i]);
    
21.         }
    
22.         return res;
    
23.     }
    
24. };

复制代码