546. Remove Boxes

[zeikar]

Problem link

https://leetcode.com/problems/remove-boxes/

Problem Summary

계속해서 연속된 수를 제거할 수 있고 제거한 개수의 제곱의 점수를 얻을 수 있다. 최대로 얻는 점수를 구하는 문제.

Solution

하드 중에서도 하드한 문제.

다른 사람의 풀이를 보고 풀긴 하였다.

일단 결론부터 말하면 3차원 DP 문제.
연속된 개수가 중요하므로 3차원으로 해야한다.

dp[i][j][k] = i 부터 j 까지의 최대 점수, k는 i와 같은 지금까지의 연속된 개수.
예제를 보면 알겠지만 1,3,2,2,2,3 에서 3을 앞에서 없애버리면 최대 점수가 되지 못한다. 222를 제거 후 33을 제거해야 하는데 이런 처리를 위해 k가 필요하다.

문제 난이도에 비해 코드는 간단한 편.

Source Code

from functools import lru_cache
from typing import List


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:

        @lru_cache(None)
        def solve(left: int, right: int, k: int):
            if left > right:
                return 0

            # k 를 그냥 사용
            ret = (k + 1) * (k + 1) + solve(left + 1, right, 0)

            for i in range(left + 1, right + 1):
                # i 까지 점수 계산, 그 뒤에 나온거로 합쳐서 계산            
                if boxes[i] == boxes[left]:
                    ret = max(ret, solve(left + 1, i - 1, 0) + solve(i, right, k + 1))

            return ret

        return solve(0, len(boxes) - 1, 0)