「もらうDP」と「配るDP」～どっちを使えばいいの？～

• DPの問題で、もらう形式と配る形式、どっちで実装すればいいの...？🤔
• なんかコンテストでよく見るけど、実際の違いがピンとこない...😅
• 使い分けのコツを知りたい

今回はこの2つのアプローチについてできるだけわかりやすく解説していきます

もらうDPと配るDPって何が違うの？

🎁 もらうDP（貰う遷移形式）

簡単に言うと「今の状態に到達するまでの道筋を考える」方式です。

例えば、友達の家に行くルートを考えるとき、

• 「駅からどう来れるかな？」
• 「バス停からどう来れるかな？」
  みたいに、目的地から逆算して考えるイメージです。

📦 配るDP（配る遷移形式）

こちらは「今の状態から次にどこに行けるか考える」方式です。

同じ例で言うと、

• 「自分の家からはどこに行けるかな？」
• 「そこからさらにどこに行けるかな？」
  みたいに、スタート地点から順に考えていくイメージです。

実際のコードで見てみる

簡単な例として、「階段の上り方は何通りか」という問題で比較してみます。
一歩または二歩ずつしか上れない場合です。

もらうDPバージョン

def climb_stairs_receive(N):
    dp = [0] * (N + 1)  # N段目までの上り方の数
    dp[0] = 1  # 0段目には1通り
    
    # 各段について、どこから来れるかを考える
    for i in range(1, N + 1):
        # 1段前から来る場合
        dp[i] += dp[i - 1]
        # 2段前から来る場合
        if i >= 2:
            dp[i] += dp[i - 2]
    
    return dp[N]

配るDPバージョン

def climb_stairs_give(N):
    dp = [0] * (N + 1)  # N段目までの上り方の数
    dp[0] = 1  # 0段目には1通り
    
    # 各段から、次にどこに行けるかを考える
    for i in range(N):
        # 1段上に進む場合
        if i + 1 <= N:
            dp[i + 1] += dp[i]
        # 2段上に進む場合
        if i + 2 <= N:
            dp[i + 2] += dp[i]
    
    return dp[N]

🤔 どっちを使えばいいの？

結論：ケースバイケース！でも、以下の基準で選ぶと良さそうです。

もらうDPがオススメな場合

• 最適な経路を後で復元したい時
• 遷移元の状態が少ない時
• メモ化再帰で実装したい時

配るDPがオススメな場合

• グラフの問題を解く時
• 累積和の計算をする時
• 遷移先の状態が少ない時

まとめ

どちらも同じ問題を解くためのアプローチですが、視点が違うだけです。最初は「もらうDP」から始めて、慣れてきたら「配るDP」も使えるようになると解ける問題の幅が広がります。

• もらうDP = 「今ここにいるけど、どこから来たんだっけ？」
• 配るDP = 「今ここにいるけど、次どこ行こうかな？」

こんな感じでイメージすると覚えやすいかもしれません！