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])

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)

總結

選擇問題
dfs or dp
優雅永不過時