Posted on 2023-06-25 22:34
Uriel 閱讀(38)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
遞歸 & 分治 、
閑來無事重切Leet Code
將一個二維數組分為加和相等的兩撥，問最大的和是多少（不存在的話輸出0）
遞歸DP+memorization，參考了Discussion -> https://leetcode.com/problems/tallest-billboard/solutions/3675264/python3-solution/
1 #956
2 #Runtime: 960 ms (Beats 33.33%)
3 #Memory: 121.3 MB (Beats 11.11%)
4
5 class Solution(object):
6 def tallestBillboard(self, rods):
7 """
8 :type rods: List[int]
9 :rtype: int
10 """
11 ans = {}
12 def DFS(i, dif):
13 if (i, dif) in ans:
14 return ans[(i, dif)]
15 if i >= len(rods):
16 if dif:
17 return float('-inf')
18 return 0
19 l = DFS(i + 1, dif + rods[i])
20 skip = DFS(i + 1, dif)
21 s = DFS(i + 1, abs(rods[i] - dif)) + min(dif, rods[i])
22 ans[(i, dif)] = max(l, s, skip)
23 return ans[(i, dif)]
24
25
26 return DFS(0, 0)