問題
数の三角形は、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
例
入力:
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 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。