0Pricing
Competitive Programming Academy · レッスン

障害物のある最小経路和

各セルに最小コストを引き継ぎます

「障害物のある最小経路和」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

数える問題からコストの問題へ

今度は各セルが値を持ち、右下までの最も安い経路を求めます。目的は経路の数え上げからコストの最小化へ変わります。

状態を定義する

dp[i][j]を、セル (i, j) に到達するための合計コストの最小値とします。同じグリッドで同じ移動を行いますが、個数ではなく合計を追跡します。

遷移

入ってくる2つの隣接セルのうち、コストが小さいほうを選び、現在のセルの値を加えます。このminによる選択が、漸化式の中心です。

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

障害物を示す

障害物とは、その上に立てないセルです。コストを無限大にすれば、そこを通る経路が最小になることはありません。

INF = float('inf')

ブロックを簡潔に処理する

グリッドでセルがブロックされている場合は、dpを無限大にして先へ進みます。min の処理が自然にそのセルを避けてくれます。

if blocked(i, j):
    dp[i][j] = INF
    continue

始点を確認する

始点自体がブロックされている場合、経路はまったくありません。無意味なコストを返さないよう、最初に確認します。

最初のセルを初期化する

始点には、そこへ入ってくる隣接セルがありません。そのため、コストは自分自身の値だけです。ループを開始する前にdp[0][0]を設定します。

dp[0][0] = grid[0][0]

境界を処理する

最上段には左からだけ、左端の列には上からだけ値が伝わります。グリッドの外を読み取らないよう、これらの境界を処理します。

無限大は伝播する

無限大に値を足しても無限大のままなので、完全にふさがれたセルはINFのコストを保ちます。到達不能なセルは自動的に判別できます。

結果を読み取る

最小コストは右下のセルにあります。その値がまだ無限大なら、有効な経路は存在しません。

ans = dp[m-1][n-1]
if ans == INF:
    ans = -1

ここで貪欲法が失敗する理由

小さいほうの隣接セルへ常に進むと、行き止まりになることがあります。貪欲に目の前だけを見るのではなく、全体のDPだけが最も安い経路を保証します。

クイックチェック

すべての隣接セルを個別に特別扱いせずに、経路DPでブロックされたセルを避けるにはどうすればよいでしょうか。

まとめ：障害物のある最短経路

コストの小さい隣接セルに現在のセルの値を加え、ブロックされたセルを無限大にして、右下のセルを読み取ります。そこが INF なら経路なしです。🧱

よくある質問

「障害物のある最小経路和」レッスンは無料ですか？

はい。「障害物のある最小経路和」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「障害物のある最小経路和」で何を学びますか？

各セルに最小コストを引き継ぎます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「障害物のある最小経路和」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. グリッド上の経路数え上げ
  2. 障害物のある最小経路和
  3. 最長共通部分列
  4. 編集距離を段階的に学ぶ
← Competitive Programming Academyに戻る