はじめに
- 最近、AtCoderのDPまとめコンテストに取り組んでいるけど、遷移型のDPの中には、「貰うdp（集めるdp）」「配るdp（渡すdp）」と呼ばれる種類のものが存在することを知った。他にインラインdpなんてのもあるらしいけど、難しそうなので後回し。
- 貰うdpと配るdpについては、けんちょんさんの投稿のイメージ図が分かりやすかったので、swiftで同じことをして頭に刻みつけたいと思う。
問題例
- 一つの問題を、「貰うdp」と「配るdp」の2種類で解くのが分かりやすいので、教育的な問題を解く。
- それが、ABC099のc問題となる。
- 所持金N円(最大10万円)を、コインで保有するとき、最低枚数は何枚となるか？
- コインの種類は、6と9の累乗の金額のみ（つまり、$1円、6円、6^2円、6^3円、...、9円、9^2円、9^3円、...$）
本能の赴くままにメモ化再帰
- 推移型のdpに行く前に、前回の投稿で復習したばかりのメモ化再帰で肩慣らしする。
let N = Int(readLine()!)!
let maxN = 100000 // 最大10万円
// 使えるコインの種類（10万円以下のコインのみ）
var coins = [1]
for p in [6,9] {
var coin = p
while coin <= maxN {
coins.append(coin)
coin *= p
}
}
// print(coins) -- [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
// メモ化配列
var dp = [Int](repeating:-1,count:maxN+1) //メモ化前の要素の値を-1とする
// 再帰関数 (金額n円の最小コイン枚数)
func rec(_ n:Int)->Int{
// 除外条件(借金は除外)
if n < 0 {return maxN} // min関数での拒否レートmaxN枚
// 終端条件
if n == 0 {return 0} // 0円なら当然0枚
if dp[n] != -1 {return dp[n]}
// 初期値
var ans = maxN
// 再帰ステップ
for coin in coins {
if coin > n {continue} // 金額以上のコインは除外
ans = min(ans , rec(n - coin) + 1) // 再帰呼び出し
}
dp[n] = ans // メモ化
return ans
}
print(rec(N))
- これで提出すると、10msでAC。やったね！
- でも、これで満足したら今回は何の意味もないです。次、行ってみよう！
貰うdpと配るdpのイメージ（けんちょんさんの図）
- 所持金iに対する配列dp[i]のコインによる遷移について、けんちょんさんが図にしたのが以下の図です。青い線が1円、緑の線が6円、赤い線が9円の線です。正確に書くならば、所持金ゼロ円の丸から、36円の線や、81円の線なども必要ですが、ゴチャゴチャしすぎるので省略しています。
- これに対して、貰うdpのイメージ図は以下のとおり示されています。
- また、配るdpのイメージ図は以下のとおりです。
貰うdpでの解答例
// ---（ここから上はメモ化再帰と同じ）---
// dp配列の準備
var dp = [Int](repeating:maxN,count:maxN+1) //メモ化前の要素の値をmaxN（min関数での拒否レート）とする
// 初期化
dp[0] = 0
// 遷移（貰う DP --- dp[n] に遷移を集める）
for i in 1...N {
for coin in coins{
if coin > i {continue}
dp[i] = min(dp[i] , dp[i - coin] + 1) // 遷移式
}
}
print(dp[N])
- まあ、下手な説明より、コードを見て貰うのが一番早いよね。前項のイメージ図通り、
for coin in coinsでの結果を遷移式左辺(dp[i])に集めてます。
−ここでは、遷移前がdp[i-coin]で遷移後がdp[i]。 - コレを提出すると、結果は7msで、メモ化再帰での10msより早くなりました。
配るdpでの解答例
- 遷移のコードのみ変更
// 遷移（配る DP --- dp[n] から遷移を出して行く）
for i in 0..<N { // -- かなり重要！
for coin in coins{
if i + coin > N {continue}
dp[i + coin] = min(dp[i + coin] , dp[i] + 1) // 遷移式
}
}
- 貰うdpとの差異は、まず、
for iの範囲が、1...Nではなく、0..<Nであること。貰うdpでは、dp[0]の結果をdp[1]で貰う形なので、iのスタートは1からで良い。これに対し、配るdpでは、dp[0]の結果を、dp[1]やdp[6]等に配る形なので、iのスタートは0からとなり、dp[N]の結果を配る先はないので、iはN-1までとなる。-
for coin in coinsにおける遷移では、遷移前がdp[i]で遷移後がdp[i + coin]。 - 遷移式左辺のdp[i + coin]における各coinの状態に対して、「配る」というイメージだね。
- 端的に言えば、for文の変数(例題ではcoin)が遷移式の右辺のみにあれば「貰うdp」で、遷移式の左辺にあれば「配るdp」になる。
-
- コレで提出すると、結果は7msで、貰うdpと同じ結果となった。
おわりに
- 貰うdpと配るdpについて理解できた。けんちょんさんのイメージ図が分かり易いのが良かったです。
- 多分、貰うdpとか配るdpはこれまでの競技プログラミングの解答でも使ったことがあると思うけど、頭の中で整理が付いて良かった。これで、問題の解説文に「貰うdpでは、･･･」とか書かれていても、頭がフリーズすることがなくなって嬉しいね。