最小経路和
高さ
h、幅 w の整数が格納されたグリッドが与えられたとき、左上のマスから右下のマスへ進むまでに通過する数値の合計を最小にする経路を求めます。進むことができる方向は右と下のみです。3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
入力
入力の最初の行には、2 つの整数
h と w (1 ≤ h, w ≤ 1000) が与えられます。続く
h 行には、それぞれ w 個の整数 がスペース区切りで与えられます (1 ≤ ≤ 1000)。出力
プログラムは、左上から右下のマスへ到達するまでに得られる合計値の最小値を出力してください。
例
Input | Output |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
解説
たとえば、3 → 2 → 1 → 2 → 3 → 4 という経路をたどることで、合計が 15 になります。
Hint 1
動的計画法（Dynamic Programming）の状態としては、2 次元の配列を使うことができます。
Hint 2
d[r][c] は、その行 r、列 c に到達するまでの最良の合計を表せます。なぜ貪欲法（greedy approach）ではうまくいかないのでしょうか。たとえば、常に最小の値へ向かって進むだけを繰り返すと、どんな問題が起こるでしょうか？
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB