312. Burst Balloons

[zeikar]

Problem link

https://leetcode.com/problems/burst-balloons/

Problem Summary

풍선을 터뜨릴 때 최대 점수를 구하는 문제. 터뜨릴 때는 풍선의 양쪽과 현재 값을 곱한 값이 점수가 된다.

Solution

딱 보면 해답이 나오지 않는 DP 문제. 문제를 반대로 생각해봐야 한다.
일단 문제 그대로는 이전 선택이 이후 선택에 영향을 주기 때문에 DP를 적용하기 어렵다. 다만, 풍선을 먼저 터뜨릴 것을 고르는 것이 아니고 마지막에 터뜨릴 것을 고른다고 생각하면 DP로 풀 수 있다!

솔루션 중 이해가 쉬운 그림을 가져왔다.

[1,5,8,7,4,3] 을 기준으로 7을 마지막에 터뜨린다고 생각해보자. 그러면 1, 5, 8 중 최대와 4, 3 중 최대 터뜨리는 값에 7 * 양쪽 끝을 곱하는 방식으로 정답을 구할 수 있다.

Source Code

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]

        @cache
        def solve(s, e):
            ret = 0
            for i in range(s + 1, e):
                score = nums[s] * nums[i] * nums[e]
                ret = max(ret, score + solve(s, i) + solve(i, e))

            return ret

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