すべてのチャレンジ
中級 0件解決済み 正答率0%

三角形の最大経路和

数の三角形の頂点から最下段までの経路で、和の最大値を求めます。

このチャレンジで学べること

  • 指数時間の全探索を動的計画法に置き換えられる
  • 1つ下の段の結果を組み合わせられる
  • 負の値と空の入力を正しく扱える

問題

原文(英語)を表示

数の三角形は、0 段目に1つ、1 段目に2つ、というように値が並んでいます。頂点から始めて1段ずつ下へ進み、そのたびに真下の値か、その右下の値に移ります(位置 i から i または i + 1 へ)。通った値の和が最大になる経路を見つけてください。すべての経路を試すと段ごとに計算量が2倍になりますが、最下段から上へ計算していけば2乗の計算量で済みます。

triangle_max_path_sum(triangle) を実装してください。

入力

triangle:上から下へ並べた各段。r 段目には r + 1 個の値があり、負の値も含まれます。

出力

頂点から最下段までの経路の和の最大値を返してください。三角形が空なら 0 を返します。

制約

0 ≤ 段数 ≤ 100; −1000 ≤ 値 ≤ 1000

例

例 1
入力:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

期待される出力:
expected = 28
入力:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

期待される出力:
long long expected = 28;
入力:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

期待される出力:
long expected = 28;

解説

最良の経路は 4, 7, 9, 8(位置 0, 0, 1, 2)で、和は 28 です。

例 2
入力:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

期待される出力:
expected = 4
入力:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

期待される出力:
long long expected = 4;
入力:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

期待される出力:
long expected = 4;

解説

負の値がある場合、−3, 5, 2 は 4、−3, −8, 9 は −2 となるので、答えは 4 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

最下段から始めましょう。最下段のマスからの最良の経路は、そのマスの値そのものです。

ヒント 2

あるマスからの最良の経路は、そのマスの値に、下の2マスの最良値のうち大きいほうを足したものです。

ヒント 3

すべての段を下から上へ処理すると、頂点のマスに答えが入ります。

目安の計算量

時間 O(rows²)、追加メモリ O(rows)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。