状態と遷移を定義する
dp[i] が何を意味するか正確に定義します
「状態と遷移を定義する」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
DPの核心
すべてのDPは、まず状態を定義することから始まります。dp[i] は実際に何を表すのでしょうか？この説明を正しく書ければ、残りも自然に決まります。
状態は正確に定義する
意味を言葉で書きます。dp[i] = 最初の i 個の要素に対する答え。この状態定義が曖昧だと、誤った漸化式につながります。
dp[i] = best total using items 0..i-1遷移
遷移は、dp[i] をそれより前の状態からどのように作るかを示します。解法の核心となる漸化式です。
dp[i] = dp[i-1] + dp[i-2]基底ケースが土台になる
基底ケースは、直接答えが分かる最小の状態です。正しい土台がなければ、その後のすべての値が少しずつ誤っていきます。
dp[0] = 1計算順序を決める
各状態は、依存している状態を計算した後に埋める必要があります。この依存関係によって、ループの方向が決まります。
for i in range(1, n+1): ...答えはどこにあるか
最終結果を保持するセルを決めます。多くの場合はdp[n]ですが、テーブル全体の最大値を求める場合もあります。
answer = dp[n] # or max(dp)状態数を数える
異なる状態の数によって時間計算量の予算が決まります。n個の要素に対する1次元DPでは、埋める状態数はO(n)です。
遷移ごとのコスト
合計時間は、状態数と遷移ごとの処理量の積です。n個の状態それぞれでO(n)の遷移を行うと、O(n squared)になります。
必要に応じて次元を追加する
1つのインデックスで状況を表せない場合は、もう1つ追加します。2次元目を加えると、dp[i] はdp[i][j]になります。
dp = [[0]*(c+1) for _ in range(n+1)]選択を復元する
実際の解を復元するには、各状態でどの遷移が選ばれたかを保存し、答えから逆向きにたどります。
choice[i] = "take"再利用できるチェックリスト
状態、遷移、ベースケース、順序、答え。この5つを明確にすれば、ほとんどのDPの漸化式は自然に組み立てられます。
確認問題
DPを設計しています。dp[i]は何を表しますか。
まとめ：名前を付けてから解く
これで状態を定義し、その遷移を書き、ベースケースを設定し、答えの場所を特定できるようになりました。この設計図によって、DPは当てずっぽうではなく手順として解けるようになります。
よくある質問
「状態と遷移を定義する」レッスンは無料ですか？
はい。「状態と遷移を定義する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「状態と遷移を定義する」で何を学びますか？
dp[i] が何を意味するか正確に定義します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「状態と遷移を定義する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- メモ化と tabulation の比較
- 状態と遷移を定義する
- 階段登りとコインの組み合わせ
- 最長増加部分列