<Hard> Burst Balloons (LeetCode : C#)

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

📕 문제 설명

nums 배열의 숫자가 쓰여진 n개의 풍선이 있다. 모든 풍선을 터뜨릴 때 최대로 얻을 수 있는 코인 반환하기

i번째 풍선을 터뜨리면 nums[i-1] * nums[i] * nums[i+1] 코인을 얻는다. (i-1이나 i+1이 nums 배열 바깥이면 1로 처리)

• Input
  nums 배열
• Output
  최대로 얻을 수 있는 코인

예제

풀이

먼저 터뜨리는 풍선을 기준으로 접근하면 왼쪽 오른쪽 subproblem으로 나눠지지 않는다. (서로 인접한 형태이므로) 그래서 정의를 할 때 시간을 거꾸로 생각해야 subproblem으로 나눠진다. 마지막에 터뜨릴 풍선을 정의하면 해당 풍선 기준으로 왼쪽과 오른쪽 문제로 나눠진다!

점화식은 다음과 같이 세워진다.
dp[i,j] = i~j까지의 풍선들에 대한 max coin
k번이 마지막에 터뜨려야한다면 i~(k-1)과 (k+1)~j로 나눠진다.
따라서 (dp[i,j] = dp[i][k-1] + dp[k+1][j] + k번 터뜨렸을 때의 coin)이다.

public class Solution {
    public int MaxCoins(int[] nums) {
        int[] balloons = new int[nums.Length + 2];
        balloons[0] = 1; // 양끝 1 추가 (처음)
        for (int i = 1; i <= nums.Length; i++)
        {
            balloons[i] = nums[i - 1];
        }
        balloons[nums.Length + 1] = 1; // 양끝 1 추가 (끝)

        int n = balloons.Length;
        int[][] dp = new int[n][];
        for (int i = 0; i < n; i++)
        {
            dp[i] = new int[n];
        }

        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 2; j < n; j++)
            {
                if (j - i == 2) // i, k, j => 터뜨려서 점수 계산하는 케이스 
                {
                    dp[i][j] = balloons[i] * balloons[i + 1] * balloons[j];
                }
                else
                {
                    dp[i][j] = Int32.MinValue;
                    for (int k = i + 1; k <= j - 1; k++) // max coin으로 갱신 
                    {
                        dp[i][j] = Math.Max(dp[i][j], balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

결과