ferinの競プロ帳

競プロについてのメモ

動的計画法

蟻本の動的計画法の漸化式を求める方法を実践してみたメモ

例1 ABC021のD問題
abc021.contest.atcoder.jp

 まず深さ優先探索で全探索を行う。a_i = numのときの取りうるパターン数を返す関数dfs(i, num)をつくり再帰処理を用いて計算しました。

# DFS
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000000007

# a_i = numのときに取りうるパターン数を返す
def dfs(i, num):
    count = 0

    # パターン数は1で確定
    if(i == k):
        return 1

    # a_i+1のときに取りうる状態をすべて試す
    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    return count % mo

ans = 0
# a_1 = 1, 2, 3, … , n について探索
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

 次にメモ化再帰の形に書き換えます。記録用の変数dp[i][j]を用意してdfs(i, num)のときの結果をdp[i][num]に保管します。

# メモ化再帰
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
mo = 1000000007

def dfs(i, num):
    count = 0
    # 1 <= i、1 <= a_i なので0から始まる配列に合わせて-1
    # すでに一度探索していれば保管された変数を返す
    if(dp[i-1][num-1] != 0):
        return dp[i-1][num-1]

    if(i == k):
        return 1

    for j in range(n-num+1):
        count = (count + (dfs(i+1, num+j) % mo)) % mo

    # dfs(i, num) の返り値を保存
    dp[i-1][num-1] = count % mo
    return count % mo

ans = 0
for i in range(1, n+1):
    ans = (ans + dfs(1, i)) % mo
print(ans)

ここで変数dp[i][j]がどのように変化しているのかを見てみると、

dp[k-1][j] = 1
dp[i][j]   = dp[i+1][j]  (j == n-1)
             dp[i+1][j] + dp[i][j+1]  (j != n-1)

という漸化式で表せます。
i == kのときはjの値にかかわらず1パターンしかありえません。また、表の右及び下の値の和がそのマスの値になります。そこで再帰を用いた表現を使わずに2重ループを用いることで表せることがわかります。

f:id:ferin_tech:20161202190217p:plain

# 動的計画法
n = int(input())
k = int(input())

dp = [[0 for i in range(n)] for j in range(k)]
# i == k-1のときは全て1
for i in range(n):
    dp[k-1][i] = 1

mo = 1000000007

# 漸化式に従って計算 右下から左上の方向へ探索
for i in range(1, k):
    _i = k-i-1
    for j in range(n):
        _j = n-j-1
        # 一番右の列のとき
        if(_j == n-1):
            dp[_i][_j] = dp[_i+1][_j] % mo
        # それ以外の時
        else:
            dp[_i][_j] = (dp[_i+1][_j] + dp[_i][_j+1]) % mo

ans = 0
for i in range(n):
    ans = (ans + dp[0][i]) % mo

print(ans)