動的計画法が有効な問題
動的計画法（DP）は、大きな問題を小さな部分問題に分け、いったん求めた部分問題の答えを保存して再利用することで計算を効率化する手法です。正解は「同じ部分問題が何度も現れ、部分問題の解を再利用できる」です。 (選択肢1が正しい)
正解の理由
動的計画法（DP）は、大きな問題を小さな部分問題に分け、いったん求めた部分問題の答えを保存して再利用することで計算を効率化する手法です。正解は「同じ部分問題が何度も現れ、部分問題の解を再利用できる」です。
仕組み・頻出ポイント
- 重複部分問題と最適部分構造がキーワードです。
- メモ化再帰（トップダウン）と表を埋める方法（ボトムアップ）の二つの実装スタイルがあります。
- フィボナッチ数列、編集距離、最短経路、ナップサック問題などが代表例です。
G検定で覚えるべきこと
単純な再帰は同じ計算を何度も繰り返すことがあります。DPはその重複を避けるために計算結果を保持します。一方で、部分問題がほとんど再利用されない問題では、表を作るオーバーヘッドだけが増えることもあります。G検定では、厳密なコードより「再利用」「表」「部分問題」という語に反応できることが重要です。
他の選択肢の評価
- 選択肢1: 正解です。重複する部分問題の解を保存して使い回すのがDPの本質です。
- 選択肢2: 完全に独立で再利用できないなら、DPの利点は小さくなります。
- 選択肢3: 目的関数が線形であることは線形計画など別の文脈の条件です。
- 選択肢4: 入力が画像かどうかはDPの適用条件ではありません。
実務での見方
実務では、動的計画法は計算を速くするだけでなく、問題の状態をどう定義するかを整理する手法でもあります。状態数が増えすぎるとメモリ使用量が大きくなるため、必要な状態だけを保持する工夫も重要です。再帰、メモ化、表という言葉を結びつけて理解してください。
確認観点
確認観点としては、状態、遷移、初期条件、再利用する値です。DPは名前よりも、同じ計算を避けるために表やメモを使うという目的を理解すると、再帰や全探索との違いが明確になります。
結論として、この問題では「用語の定義」だけでなく、どの前提で使えるのか、どの誤解を避けるべきか、実務では何を確認するのかまで結びつけて理解することが重要です。