leetcode:面試題 08.13. 堆箱子【自頂而下的dfs + memory or 自底而上的排序 + dp】

白速龍王的回眸 2022-06-23 16:24:36 阅读数:483

leetcode08.13.箱子dfsmemory

在這裏插入圖片描述

分析

這種按要求選取元素的題目往往有兩種思路
分別是自頂而下的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
優雅永不過時

版权声明:本文为[白速龍王的回眸]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/174/202206231538312237.html