yambe2002 https://blog.hatena.ne.jp/yambe2002/ yambe2002’s diary https://yambe2002.hatenablog.com/ 苦戦したのでメモしておく。 n個の風船が１列に並んでいて、それぞれにスコアが設定されている。風船を割ると「左のスコア x この風船のスコア x 右のスコア」だけ得られる。割る順番を工夫して、最終的なトータルスコアを最大化せよ。 ・「左のスコア」「右のスコア」はなかったら1 ・割った風船は詰める 0 1 https://leetcode.com/problems/burst-balloons/ トップダウンでやると計算量がO(N!)となり間に合わない。ボトムアップで考える。 dp[l][r]: nums[l...r]での最大スコア とする。 この範囲で最後にx番目を割るとき、そこで得られるスコア… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyambe2002.hatenablog.com%2Fentry%2F2020%2F08%2F01%2F054112" title="LeetCode 312. Burst Balloons - 解法メモ - yambe2002’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-08-01 05:41:12 rich https://yambe2002.hatenablog.com/entry/2020/08/01/054112 1.0 100%