動的計画法
蟻本の動的計画法の漸化式を求める方法を実践してみたメモ
例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重ループを用いることで表せることがわかります。
# 動的計画法 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)