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

Rétrospective du roi dragon blanc 2022-06-23 16:24:41 阅读数:976

leetcodequestionentrevue08.13.empiler

Insérer la description de l'image ici

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

版权声明:本文为[Rétrospective du roi dragon blanc]所创,转载请带上原文链接,感谢。 https://qdmana.com/2022/174/202206231538312237.html