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]