DPは「同じ続きをまとめる」

動的計画法では、そこまでの詳細を全部覚える代わりに、今後必要な情報だけを状態にします。

言語：Python / 計算量：状態数 × 各遷移数

前提：ビット全探索で部分集合を列挙

考え方

1. dp[i] が何を意味するか日本語で1文にします。
2. 初期値と到達不能の値を分けます。
3. 小さい状態から遷移し、答えの場所を決めます。

具体例

1段か2段上る階段。i段への到着はi-1段かi-2段から。dp[0]=1 とすると dp[1]=1, dp[2]=2, dp[3]=3。

実装

n = 4
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n+1):
    dp[i] = dp[i-1]
    if i >= 2:
        dp[i] += dp[i-2]
print(dp[n])

注意する条件

最小値DPの未到達を0にすると、存在しない経路が最良に見えてしまいます。十分大きい値を使います。

確認問題

1段か2段で3段上る方法は何通り？

実装課題

N (0 ≤ N ≤ 1000) 段を1段か2段ずつ上る方法数を 998244353 で割った余り。0段は1通り。

入力:
4
出力:
5

n = int(input())
mod = 998244353
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = dp[i-1]
    if i >= 2:
        dp[i] = (dp[i] + dp[i-2]) % mod
print(dp[n])

実戦につなげる補講

一度に全て読まなくて大丈夫です。今日は1節と1問から。

状態は「未来の判断に必要な情報」

同じ場所に着く経路が何通りもあっても、その後に選べる行動が同じなら、最小費用だけを保存できます。「どこにいるか」以外に残り回数や直前の選択で未来が変わるなら、その情報も状態へ含めます。

状態数×遷移数で計算量を出す

dp[i]を位置iまでの最小費用とし、各iから2通りだけ移動するなら状態N個×2でO(N)。各iからK通りならO(NK)。DPという名前だけでは高速とは言えません。

5点を先にメモする

①dpの1マスの意味。②開始位置だけ0、それ以外は到達不能。③どの状態から何を足すか。④依存元を先に計算する順序。⑤どのマスが答えか。コードに入る前にこの5点を埋めます。

経路列挙から状態へ圧縮する

1歩か2歩ずつ進む方法を全列挙すると、同じ位置以降の計算を何度も繰り返します。小さい位置から順にdpを確定すれば、その続きは一度ずつ計算すれば済みます。負の費用があっても、前方だけに進むこの依存関係なら処理順序は保たれます。

段階式の追加演習

1. 状態を一文にする

位置0からNへ1歩か2歩で進む。位置iに入る費用がcost[i]。何をdp[i]に保存する？

2. 実装：通行費の最小

cost[0]=0、長さは1以上。1つまたは2つ先へ進み、到着先のcostを払う。末尾までの最小費用min_feeを書いて。

def min_fee(cost):
    dp = [float("inf")] * len(cost)
    dp[0] = 0
    for i in range(1, len(cost)):
        dp[i] = dp[i - 1] + cost[i]
        if i >= 2:
            dp[i] = min(dp[i], dp[i - 2] + cost[i])
    return dp[-1]

3. 遷移数が増えたら

N=200000で各位置から最大K=200000個先へ遷移できる。DPなら間に合うと言える？

4. 状態が足りない例

同じ位置でも「2歩ジャンプを既に使ったか」で次の行動が変わる。dp[i]だけで十分？

公式過去問への橋渡し

Educational DP Contest A / 公式問題

まず状態・初期値・遷移・順序・答えを自分で書き出す。本サイトの通行費問題とは費用の定義が違う点も確認する。

見本を閉じて確認

• 何を繰り返しているかを説明できる
• 使える条件と使えない条件を1つずつ言える
• 見本を閉じて実装し、小さい入力で確かめられる

読了の記録・下書き・メモへ

関連する公式資料・課題