[leetcode #312] Burst Balloons

Problem

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] nums[i] nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

・ n == nums.length
・ 1 <= n <= 500
・ 0 <= nums[i] <= 100

Idea

비록 풀지는 못 했지만 최근 본 문제 중에선 가장 흥미롭고 도움이 많이 되는 문제인 듯하다.

문제 내용을 보면 (당연히) dynamic programming을 사용하며, sliding window 개념까지 응용해서 풀 수 밖에 없다는 걸 알 수 있다. 그런데 dp 식을 만들기가 까다로워 난이도가 Hard인 듯 하다.

풍선을 터뜨릴 때 얻을 수 있는 값은 터뜨리는 풍선의 왼쪽 풍선과 오른쪽 풍선, 그리고 터뜨린 풍선의 값의 곱이다. 가장 왼쪽과 오른쪽 풍선을 터뜨릴 때는 왼쪽 또는 오른쪽에 1이 있다고 가정한다. 가장자리에 있는 풍선을 터뜨릴 때 값을 쉽게 계산하기 위해 n+2 크기의 array를 새로 만들고, 왼쪽 끝과 오른쪽 끝 값을 1로 정한 뒤 나머지 값을 주어진 array로 채운다.

이후 재귀함수를 호출해서 dp 값을 계산한다. 재귀함수에는 left index와 right index가 인자로 들어가며, left와 right index 차가 1일 때 sliding window가 비어있는 것이므로 0을 리턴한다.

다음으로 sliding window의 index를 옮겨가면서 현재 window의 최대값을 계산한다. left와 right 사이의 index를 차례로 탐색하는데, 이 때 index는 가장 마지막으로 선택하는 index다. 마지막으로 선택할 때 값은 arr[left] arr[i] arr[right]가 된다. 나머지 값들은 일부 범위를 선택해 재귀함수를 다시 호출해 더한다. 탐색을 한 번 거칠 때마다 최대값을 계산하며, 루프를 다 돌고나면 최대값을 dp에 저장한다.

재귀함수를 설계하고 난 뒤 [0, n+1]을 범위로 넣으면 원하는 값이 얻어진다.

아래 그림을 보면 이해하기가 쉬울 것이다. (참조는 Reference Link에 적어두었다.)

Solution

class Solution {
    int[] arr;
    int[][] memo;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        arr = new int[n+2];
        arr[0] = arr[n+1] = 1;

        for (int i=1; i <= n; i++) {
            arr[i] = nums[i-1];
        }

        memo = new int[n+2][n+2];
        for (int i=0; i < n+2; i++) {
            Arrays.fill(memo[i], -1);
        }

        return burst(0, n+1);
    }

    private int burst(int left, int right) {
        if (left + 1 == right) {
            return 0;
        }

        if (memo[left][right] != -1) {
            return memo[left][right];
        }

        int ans = -1;
        for (int i=left+1; i < right; i++) {
            ans = Math.max(ans, arr[left] * arr[i] * arr[right] + burst(left, i) + burst(i, right));
        }
        memo[left][right] = ans;

        return ans;
    }
}

Reference

https://leetcode.com/problems/burst-balloons/
https://leetcode.com/problems/burst-balloons/discuss/1659162/JAVA-or-DP-or-Divide-and-Conquer-or-Sliding-Window-or-Detailed-Explanation-Using-Image