二次元グリッドの最小経路を求める動的計画法の実装
問題の概要
左上のセル (0, 0) から右下のセル (m-1, n-1) まで、右または下のみ移動して到達する経路のうち、通過したセルの値の合計が最小となるものを求めます。
DP の定式化
dp[i][j] を「(i, j) まで到達する経路の最小値」とします。到達できる移元は上方向か左方向のみなので、次の漸化式が成り立ちます。
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
...
10月12日 23:10 投稿