グリッド上の経路数え上げ
隅から隅までの経路数を合計します
「グリッド上の経路数え上げ」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
古典的なグリッド問題
グリッドの左上から始めて、右下を目指します。1回の移動では右または下に進みます。異なる経路はいくつあるでしょうか。
DPが適している理由
すべてのセルには、上のセルまたは左のセルから到達できます。この重複部分が、まさにこれがDP問題である理由です。
状態を定義する
dp[i][j]を、始点からセル (i, j) に到達する方法の数とします。状態を明確に名前付けすることが、問題解決の半分です。
遷移
到達できるのは上または左からだけなので、その数を足し合わせます。これがテーブル全体を動かす遷移です。
dp[i][j] = dp[i-1][j] + dp[i][j-1]初期条件
始点のセルに到達する方法は、何もしないという1通りだけです。したがって、ほかを埋める前にdp[0][0]を1にします。
dp[0][0] = 1端には経路が1つだけある
最上段または左端の列にあるセルには、まっすぐ進む経路が1つだけあります。隣の一方がグリッドの外にあるため、その個数は常に1です。
テーブルを作る
0で埋めたm × nのテーブルを作ります。最初にサイズを決めておくと、インデックスを扱いやすくなり、予期しない問題も避けられます。
dp = [[0] * n for _ in range(m)]読み取り順に埋める
行を上から下へ、各行の列を左から右へループします。この順序なら、使う前に両方の隣接セルが準備されています。
for i in range(m):
for j in range(n):
...答えのセル
すべて埋め終えると、経路の数は最後のセルに入っています。答えは右下の dp[m-1][n-1] です。
answer = dp[m-1][n-1]1行でメモリを節約する
各行で必要なのは直前の行だけなので、1行だけ保持して、その場で更新できます。これによりメモリ使用量を O(n) に減らせます。
row[j] += row[j-1]数学による近道
障害物がなければ、答えは二項係数です。全移動回数のうち、下方向に進む回数を選びます。障害物が現れると、DPのほうが有効です。
クイックチェック
通行可能な内部セル dp[i][j] を埋めています。正しい式はどれでしょうか。
まとめ：経路の数え上げ
セルまでの経路数として dp を定義し、dp[0][0] を1に設定して、上のセルと左のセルを足します。右下のセルに答えが入ります。🧭
よくある質問
「グリッド上の経路数え上げ」レッスンは無料ですか？
はい。「グリッド上の経路数え上げ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「グリッド上の経路数え上げ」で何を学びますか？
隅から隅までの経路数を合計します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「グリッド上の経路数え上げ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- グリッド上の経路数え上げ
- 障害物のある最小経路和
- 最長共通部分列
- 編集距離を段階的に学ぶ