23.01.03 Today’s Leetcode
944. Delete Columns to Make Sorted (easy)
class Solution:
def minDeletionSize(self, strs: List[str]) -> int:
n = len(strs)
m = len(strs[0])
count = 0
for i in range(m):
for j in range(n - 1):
a, b = ord(strs[j][i]), ord(strs[j + 1][i])
if a > b:
count += 1
break
return count
Tallest Billboard (hard)
lee 선생님의 설명 : 링크
요약하자면 dp[d]의 의미는 두 쌍의 합이 d
만큼 차이나는 경우에서 큰 숫자. dp[0]을 뽑는게 우리의 목표이고
케이스를 나눠서 dp를 update해서 결과를 도출한다.
class Solution:
def tallestBillboard(self, rods):
dp = {0: 0}
for x in rods:
for d, y in dp.items():
dp[d + x] = max(dp.get(x + d, 0), y)
dp[abs(d - x)] = max(dp.get(abs(d - x), 0), y + min(d, x))
return dp[0]