Leetcode: interview question 08.13 Stacking bin [top-down DFS + memory or bottom-up sorting + DP]

analysis

There are often two ways to choose elements according to requirements
From the top down dfs + memory Very elegant
And bottom-up sorting + dp Also is very elegant

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


        #  Longest ascending subsequence variant 
        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)

summary

Choice problem
dfs or dp
Elegance never goes out of style