【第三轮】8.3-8.9 CareerCup 9.10

9.10 You have a stack of n boxes, with widths w1, heights  h1 and depths d1. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box




回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
Try every box as the bottom of the stack and compute the max height. The intermediate result can be stored to eliminate the redundant computation.


【时间复杂度】
O(n^2)


【空间复杂度】
O(n)

【gist link】
https://gist.github.com/happyWinner/9516365012959289bbb4

【解题思路】
find the tallest stack with each single box as the bottom, respectively, recursively solve the height while store the intermediate results.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/9b0c648aacdb1d52ae11

【解题思路】
Recursion + memorization of result

【时间复杂度】
O(N^2)

【空间复杂度】
O(N^2) if use hashmap

【gist link】
https://gist.github.com/chrislukkk/e5f3a99557876b12657d

【解题思路】try to find the height of each combination with a single box, update the max height recorder in the process
【时间复杂度】
O(N!)
【空间复杂度】
O(N^2)
【gist link】
https://gist.github.com/bitcpf/6c34a58caf0fcc633f0e

我有一个问题

     maxStack.addFirst(bottom);
    map.put(bottom, maxStack);  

然后方法一开始时候检查bottom在里面的话直接return maxStack 但是这时候maxStack已经有bottom当做底了 然后return回来 到最下面又 add bottom 不是反复用了2个bottom当底么？