leetcode：面试题 08.13. 堆箱子【自顶而下的dfs + memory or 自底而上的排序 + dp】

分析

这种按要求选取元素的题目往往有两种思路
分别是自顶而下的dfs + memory 非常优雅
以及自底而上的排序 + dp 也很优雅

dfs + memory

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        # sol(w, d, h) => if we choose(w, d, h), what's our maxHeight
        @cache
        def dfs(w, d, h):
            choices = [(nw, nd, nh) for nw, nd, nh in box if nw < w and nd < d and nh < h]
            if not choices: return h # we can not dfs
            return h + max([dfs(nw, nd, nh) for nw, nd, nh in choices]) # dfs
        
        # outer entry
        return max([dfs(w, d, h) for w, d, h in box])
1
2
3
4
5
6
7
8
9
10
11

sort + dp

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        box.sort()
        n = len(box)
        # dp[i] => box[i] as bottom maxHeight
        dp = [box[i][2] for i in range(n)]


        # 最长上升子序列变种
        for i in range(n):
            for j in range(i):
                # check all j before i
                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:
                    # if i can add after j
                    dp[i] = max(dp[i], dp[j] + box[i][2])
                    #print(i, dp[i])
        
        #print(dp)
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

选择问题
dfs or dp
优雅永不过时