naoya_t@hatenablog

いわゆるチラシノウラであります

LeetCode: 312. Burst Balloons

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

LeetCodeのTop 100 Liked Questionsを埋めてて最後に食べ残して*1解説ACした問題。

ざっくり訳すと

風船がn個あり、0n-1 の番号が振られている。i番目の風船には番号 a_i が書かれている。
すべての風船を割るように頼まれているが、風船を1つ割るときに

  • 割る風船に書かれている番号
  • その風船のすぐ左にある風船に書かれている番号(左に風船が存在しなければ代わりに1)
  • その風船のすぐ右にある風船に書かれている番号(右に風船が存在しなければ代わりに1)

の3つの数の積と等しい枚数のコインがもらえる。(風船を割ると、そのすぐ左・すぐ右にあった風船は隣りあうことになる)

風船を割る順序を賢く選んだときもらえるコインは最大何枚か。

制約:
0\le n\le 500
0\le a_i\le 100

といった問題。
5万2千人ほどにしか解かれていなくて、Top 100 Liked Questionsの中では難しめなのだと思われる。

  • 小さい順に貪欲に割る → そもそもサンプルケースがそうなってないだろ
  • (もうちょい賢く)_nC_3通りの組み合わせの積を昇順に並べて真ん中のやつを割る →そもそもサンプル(略
  • 1ステップごとにどれを割るかのチョイスを回して1つ下の状態から求めていくメモ化再帰(ないしDP)をするのか… → ビットで表現しても2^nパターンの集合があってn=500はきついのでは

その辺りまで考えてタイムアップ(というかギブアップ)。
解説(公式ではなくユーザによるもの)を読んだ
For anyone that is still confused after reading all kinds of explanations...

  • dp[左][右] : 「左」から「右」までのすべての風船を割って得られる最大コイン数 を意味する
    • dp[0][n-1] が求める答え(上記の解説では右がinclusive
  • dp[左][右] = 左\le k\le 右 における、dp[左][k-1] + (a_{左-1}\cdot a_k\cdot a_{右+1}) + dp[k+1][右] の最大値

ああなるほど、区間_nC_2通りだし、区間 vs 区間で状態遷移するDPに落とせばいいのか…(こういう発想がなかなか出てこないなあ… ABC/ARCだったらD問題(400〜500点)ぐらいに来てもおかしくなさそうなレベル感なのだけれど)
一応サンプルケースを手計算で回してみて数が合うのを確認してから
実装(簡単)して
→AC

class Solution {
public:
    int maxCoins(vector<int>& a) {
        int L = a.size();
        if (L == 0) return 0;
        
        vector<vector<int>> dp(L+1, vector<int>(L+1, 0));  // dp[i][j] : [i,j)
        
        for (int w=1; w<=L; ++w) {
            for (int i=0; i+w<=L; ++i) {
                // dp[i][i+w]
                int best = 0;
                for (int k=0; k<w; ++k) {
                    int x = (0<i ? a[i-1] : 1) * a[i+k] * (i+w<L ? a[i+w] : 1);
                    x += dp[i][i+k] + dp[i+k+1][i+w];                                      
                    best = max(best, x);
                }
                dp[i][i+w] = best;
            }
        }
        return dp[0][L];
    }
};

*1:鍵がかかっていて有料会員しか開けない問題が1つあるけどそれとは別。