区間の
並んだ
海外で定番の問題リスト 4 本には入っていません
問題
一列にnums でnums[i] は
- 割った
風船は 列から 消え、 その 左右の 風船が 新しく 隣どうしになります - 左か右に
風船が 残っていない ときは、 そちらの 数を 1 として掛けます numsの長さは 1 以上 100 以下で、 どの 数も 0 以上 100 以下の整数です
入力と出力の例
例 1
まん中の 1 を
例 2
2 を
例 3
風船が 1 つなら、
面接での聞かれ方
面接では、
- 「風船を
割る 順を 決めて、 得点の 合計を 最大に してください」 - 「最初に割る風船」で
分けようとして 詰まった 所で、 「最後に 割る 風船で 考えたら？」と 促される ことがあります - 書き終えると
「表を埋める順は？」 「計算量は？」と 聞かれます
最初に
ヒント
まだ開いていません
付箋は 4 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3
ヒント 4答えに近い
アルゴリズムのチートシートの「動的計画法 (DP)」に、
関わる学び
動的計画法は、
まず
段 1
割る
段 2
両端にv をv[l] と v[r] のbest[l][r] とv[l] と v[r] に
段 3
k よりbest[l][r] は、best[l][k] + best[k][r] + v[l] × v[k] × v[r] の
段 4
best[l][r] には、best[0][n+1] です。
解答
Python
Python
def cut(v, dp, l, r):
edge = v[l] * v[r]
top = 0
for k in range(l + 1, r):
a = dp[l][k] + dp[k][r]
a += edge * v[k]
top = max(top, a)
dp[l][r] = top
def max_burst(nums):
v = [1] + nums + [1]
n = len(v)
dp = [[0] * n for _ in v]
for g in range(2, n):
for l in range(n - g):
cut(v, dp, l, l + g)
return dp[0][n - 1]JavaScript
JavaScript
function cut(v, dp, l, r) {
const edge = v[l] * v[r];
let top = 0;
let k = l + 1;
while (k < r) {
let a = dp[l][k];
a += dp[k][r];
a += edge * v[k];
top = Math.max(top, a);
k++;
}
dp[l][r] = top;
}
function maxBurst(nums) {
const v = [1, ...nums, 1];
const n = v.length;
const dp = v.map(
() => Array(n).fill(0),
);
for (let g = 2; g < n; g++) {
let l = 0;
while (l + g < n) {
cut(v, dp, l, l + g);
l++;
}
}
return dp[0][n - 1];
}Go
Go
func cut(
v []int, dp [][]int, l, r int,
) {
edge := v[l] * v[r]
top := 0
for k := l + 1; k < r; k++ {
a := dp[l][k] + dp[k][r]
a += edge * v[k]
top = max(top, a)
}
dp[l][r] = top
}
func maxBurst(nums []int) int {
v := append([]int{1}, nums...)
v = append(v, 1)
n := len(v)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for g := 2; g < n; g++ {
for l := 0; l+g < n; l++ {
cut(v, dp, l, l+g)
}
}
return dp[0][n-1]
}dp はbest のcut は、v[l] と v[r] のk をdp[l][r] にedge はg はdp[l][k] と dp[k][r] (どちらもg より
計算量
- 時間は O(n³) です (n は
風船の 数)。 区間が 約 n² / 2 個 あり、 それぞれで 最後に 割る 風船を 最大 n 通り試します。 100 個なら 区間は 約 5000 個、 試す回数は 全部で 約 17 万回です - 使う
記憶は O(n²) です。 区間ごとの 答えの 表を持ちます - 覚えておく
再帰 (メモ) で 上から 書いても、 時間と 記憶は同じです
よく
- 最初に
割る 風船で 区間を分ける。 最初に 割った 後は、 その 左右の 風船が 隣どうしに なるので、 左と 右の 区間を 別々に 考えられません。 最後に 割る 風船で分けます - 小さい
数から 順に 割る欲張り。 例 2 は 小さい 順 (2、 4、 6) に 割っても 78 で 合いますが、 [3, 0, 4, 2]で小さい 順に 割ると 0 + 8 + 12 + 4 で 24 に なり、 0、 4、 2、 3 の 順に 割る 0 + 24 + 6 + 3 の 33 に 届きません。 欲張りが 合うかは 入力しだいなので、 表で 全部の 分け方を比べます - 見えない
両端の 1 を 足し忘れる。 端の 風船を 割る 時に 1 を 掛ける 決まりを、 場合分けで 書くと 漏れやすくなります。 両端に 1 を 足しておけば、 全部の 場合が 同じ式で書けます
解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日
面接での
書き始める
「両端に
数 1 の 風船を 足します。 区間の 中で 最後に 割る 風船 k を 決めると、 その ときの 両隣は 区間の 両端で、 k の 左と 右は 別々の 区間として 先に 割り 終わっています。 なので 区間の 答えは、 左の 答え + 右の 答え + 両端 × k の 最大です。 幅の 小さい 区間から 埋め、 時間は O(n³)、 記憶は O(n²) です。」
書き終えたら、
「例 1 の
[9, 1, 9]は、両端を 足して [1, 9, 1, 9, 1]です。左の 9 を 最後に 割るとします。 その前に 右の 1 と 9 を 割り終えていて、 その 区間の 最大は、 1 を 先に 割る 9 × 1 × 9 の 81 と、 次に 右の 9 を 割る 9 × 9 × 1 の 81 で 162 です。 最後の 9 は 両隣が 1 で 9、 合わせて 171 です。 まん中の 1 を 最後に すると 9 + 9 + 1 の 19 に しかなりません。」