Leetcode: question d'entrevue 08.13. Empiler la boîte [DFS en haut + mémoire ou tri en bas + DP]

Analyse

Ce sujet de sélection d'éléments sur demande a souvent deux idées
De haut en bas.dfs + memory Très élégant.
Et l'ordre du bas vers le haut + dp Et élégant

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


        #  Variation de la séquence ascendante la plus longue 
        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)

Résumé

Sélectionner les questions
dfs or dp
L'élégance n'est jamais démodée