LeetCode 312. Burst Balloons - 解法メモ

苦戦したのでメモしておく。

n個の風船が１列に並んでいて、それぞれにスコアが設定されている。風船を割ると「左のスコア x この風船のスコア x 右のスコア」だけ得られる。割る順番を工夫して、最終的なトータルスコアを最大化せよ。
・「左のスコア」「右のスコア」はなかったら1
・割った風船は詰める
0 <= nums[i] (風船iのスコア) <= 100
1 <= n <= 500

https://leetcode.com/problems/burst-balloons/
トップダウンでやると計算量がO(N!)となり間に合わない。ボトムアップで考える。
dp[l][r]: nums[l...r]での最大スコア
とする。
この範囲で最後にx番目を割るとき、そこで得られるスコアは
nums[l-1] * nums[x] * nums[r+1]
となる。
さらに、左右のdp[l][x-1]とdp[x+1][r]は独立に考えてよいことがわかる。
なぜなら、xは最後に壊されるので、たとえば左ブロック[l, x-1]はx+1番目から右は関係ない。
よって、
dp[l][r] = Max(dp[l][r], dp[l][x-1] + dp[x+1][r] + nums[l-1] * nums[m] * nums[r+1])
となる。
あらかじめnums[]の先頭と末尾に1を挿入しておくと実装が楽。

public class Solution
{
    public int MaxCoins(int[] nums)
    {
        nums = new int[] { 1 }.Concat(nums).Concat(new int[] { 1 }).ToArray();
        var dp = new int[nums.Length, nums.Length];

        for (int gap = 0; gap < nums.Length; gap++)
        {
            for (int l = 1; l < nums.Length - 1; l++)
            {
                var r = l + gap;
                if (r >= nums.Length - 1) continue;

                var val = 0;
                for (int x = l; x <= r; x++)
                    val = Math.Max(val, nums[l - 1] * nums[x] * nums[r + 1] + dp[l, x - 1] + dp[x + 1, r]);
                dp[l, r] = val;
            }
        }

        return dp[1, nums.Length - 2];
    }
}