LeetCode: Burst Balloons

처음에 문제 보고 재귀로 돌렸더니 시간 초과 떴다
보통 재귀로 돌려도 되는데 재귀에서 시간 초과 뜨는 문제는 DP로 풀렸었던 경험이 있어서 DP로 노선을 바꿨다.
DP 넘 싫어..

문제 풀이

• 우선 nums 배열이 비어있을때 처리를 해줬다.

• 맨 처음이나 마지막 풍선을 터트릴때에는 nums 배열의 길이를 넘어가게 되고 그런 경우는 1이 그려진 풍선이 있다고 처리하라고 문제에 나와 있다.
  그래서 그 부분은 nums 배열보다 길이가 2 많은 배열을 선언해 맨 처음과 마지막에 1을 넣어준 배열을 만들어줬다.

• 2차원 dp 배열을 통해 풍선 3개를 택한 coin을 계산해줬다.

import java.util.*;
class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] values = new int[n + 2];
        values[0] = 1;
        values[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            values[i] = nums[i - 1];
        }
        
        n = values.length;
        int[][] dp = new int[n][n];
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = len + i - 1;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}