アルゴリズムとプログラミングアルゴリズムとデータ構造

動的計画法（DP）に関する記述として、最も適切なものはどれか。

ア.問題を再帰的に小問題に分割し、解の重複計算を避けるため小問題の解を表に保存して再利用する手法正解

イ.局所的に最も良い選択を繰り返すことで、必ず大域最適解を得る手法

ウ.問題の解候補をランダムに選び、評価関数で良いものを残す確率的手法

エ.問題を変えずに何度も同じ計算を繰り返し、安定した解に収束させる手法

解説

DP は「同じ部分問題を二度解かない」のがコツ。一度解いたら答えをメモ帳に貼って、次に呼ばれたらノートを見る——フィボナッチ高速化が代表例です。

なぜアが正解か

アが正解。動的計画法は「最適部分構造」と「部分問題の重複」をもつ問題に対し、部分問題の解を表（メモ）に蓄えて再利用することで指数時間を多項式時間に圧縮する手法です。ナップサック問題や編集距離、最長共通部分列などが典型例。

なぜイは間違いか

これは「貪欲法（greedy algorithm）」の説明ですが、必ず大域最適に至るとは限らない点で誤り。貪欲法が DP に勝るのは構造に特殊な性質（マトロイドなど）がある場合だけです。

なぜウは間違いか

これは遺伝的アルゴリズムや焼きなまし法など「メタヒューリスティクス」系の発想。動的計画法は決定論的に表を埋めていく手法で、ランダム性はありません。

なぜエは間違いか

これは反復法や定点反復の説明に近いもの。同じ計算を繰り返すのではなく、「異なる小問題の解を順に積み上げる」のが動的計画法です。

出典: AI生成問題（学習用）

← 前の問題

重み付きグラフにおいて、ある始点から各頂点への最短経路を求めるアルゴリズムとして適切なものはどれか。ただし、辺の重みはすべて非負とする。

次の問題 →

Boyer-Moore法（BM法）による文字列検索の特徴として正しいものはどれか。