最大落下経路和

高さ h、幅 w のグリッドが与えられたとき、上から下へと移動しながら得られる数値の合計のうち、最大になるものを求める問題です。移動は「下方向に隣接する3つのセル」のみ許されます。つまり、位置 (r, c) にいるときは (r + 1, c - 1), (r + 1, c), (r + 1, c + 1) のいずれかに進むことができます。これを「落下経路和」と呼ぶのは、グリッドの最上段から最下段まで落ちるように移動するためです。求めたいのは、この経路によって得られる合計値の最大値です。