Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. The subject

You are given a stack of n boxes, wide wiW_iwi, deep did_IDI, and high HIh_IHI. Boxes cannot be turned over, and when stacked, the boxes below must be wider, higher and deeper than the boxes above. Implement a method to build the highest stack of boxes. The height of the stack is the sum of the heights of each box.

The input uses the array [WI,di,hi][w_i, d_i, h_i][WI,di,hi] to represent each bin.

Example 1: input: box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] output: 6 example 2: input: box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] output: 10Copy the code

2.

2.1 Backtracking algorithm

First come up with the brute force solution, where each box is the bottom box. Then look for the next box among the remaining boxes, which will naturally be smaller than the previous one, and then look for a smaller one. This is a DFS process.

Having chosen one box as the base, the problem can be converted to finding the maximum height that the remaining boxes can stack under constraints. You can cache the solution to the subproblem (the maximum height you can get based on each box) to speed up the calculation. In addition, you can order the boxes in ascending order in dimensions so that none of the boxes behind the current box can be on top of it. So the operation is as follows:

  • Sort (ascending)
  • Walk through, using each box as the base
  • In the remaining boxes, with the boxes in step 2 as the base and constraints, find the appropriate boxes and repeat 2 recursively until all boxes are present. Compute the sum of heights.
  • Take the maximum in the height sum.
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [] (auto& a, auto& b){
            return a[0] < b[0];
        });
        vector<int> cache(box.size(), - 1);
        int max_height = 0;
        for(int i = 0; i < box.size(a); i++){ max_height =max(max_height, dfs(box, i, cache));
        }
        return max_height;
    }

    int dfs(vector<vector<int>>& box, int bottom_box_i, vector<int>& cache){
        if(cache[bottom_box_i] ! =- 1) {return cache[bottom_box_i];
        }
        int ret = 0;
        vector<int> &bottom_box = box[bottom_box_i];
        for(int i = 0; i < bottom_box_i; i++){
            if(small(box[i], bottom_box)){
                ret = max(ret, dfs(box, i, cache));
            }
        }
        ret = ret + bottom_box[2];
        cache[bottom_box_i] = ret;
        return ret;
    }
    
    bool small(const vector<int> &box1, const vector<int> &box2){
        for(int i = 0; i<box1.size(a); i++){if(box1[i] >= box2[i]){
                return false; }}return true; }};Copy the code

2.2 Dynamic Planning

This problem is similar to the Russian doll, both belong to the longest increasing substring problem. That is, find the increasing order of the sequence in the one-dimensional array, as shown in the figure below:

The final purple sequences 1,2, and 3 are the final longest increasing substring. So for this problem, we’re going to sort the three dimensions, and if the first dimension is the same, we’re going to increment the second dimension, and if the second dimension is the same, we’re going to increment the third dimension. Here is a two-dimensional example:

Therefore, the algorithm operation for this problem is as follows:

  • The array is first rearranged in descending order on any edge to reduce the number of inner loops.
  • Dp one-dimensional array is used to record the maximum height of the box with serial number III as the top.
  • When calculating each box III, find all boxes KKK (III can be placed on top of KKK) under constraints, and calculate the sum of the maximum height with K as the top and the height of III, and take the maximum value.
  • When all boxes are complete, take the maximum number of elements in the DP array
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [] (auto& a, auto& b){
            return a[0] < b[0];
        });
        vector<int> dp(box.size(), 0);
        dp[0] = box[0] [2];
        int ret = dp[0];
        for(int i = 1; i < box.size(a); i++){int max_height = 0;
            for(int j = 0; j < i; j++){
                if(small(box[j], box[i])){
                    max_height = max(max_height, dp[j]);
                }
            }
            dp[i] = max_height + box[i][2];
            ret = max(ret, dp[i]);
        }
        return ret;
    }
    
    bool small(const vector<int> &box1, const vector<int> &box2){
        for(int i = 0; i<box1.size(a); i++){if(box1[i] >= box2[i]){
                return false; }}return true; }};Copy the code

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream