過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

動的計画法

部分問題の答えを再利用する

動的計画法は、問題を部分問題へ分け、その結果を保存して再利用することで全体の解を求める方法です。同じ部分問題が繰り返し現れる場合に、毎回計算し直す無駄を減らせます。DPと略されます。最適化問題だけでなく、個数を数える問題や到達可能性の判定などにも利用されます。

状態と遷移

何を保存するかという状態の定義と、既に求めた状態から次の状態をどう求めるかという遷移を決めます。例えば階段を一段か二段ずつ上る方法の数なら、ある段への到達方法は一つ前と二つ前の段から来る方法に分けられます。保存する情報が不足すると正しい結果を求められず、多すぎると記憶量が膨らみます。

Pythonによる例

def count_stair_ways(steps):
    if steps < 0:
        return 0
    ways = [0] * (steps + 1)
    ways[0] = 1
    for current in range(1, steps + 1):
        ways[current] = ways[current - 1]
        if current >= 2:
            ways[current] += ways[current - 2]
    return ways[steps]

0段へは何もしない一通りがあると定義し、小さい段から順に求めています。

メモ化との関係

再帰呼出しの結果を保存する上からの方法と、必要な順序で表を埋める下からの方法があります。どちらも同じ部分問題の再計算を避ける考え方を使えます。ただし、依存関係に循環がある場合や、状態の数が非常に大きい場合は、そのまま簡単に適用できるとは限りません。

貪欲法との違い

貪欲法はその時点でよさそうな選択を確定して進みます。動的計画法は複数の部分的な候補の結果を比較し、全体につなげます。試験では、配列の各要素が何を意味するか、初期値、更新順序を確認します。同じ配列を上書きする場合は、更新済みの値を使ってよいかが重要です。計算量は状態数と一状態あたりの遷移数から考えましょう。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

用語一覧

5件