• このエントリーをはてなブックマークに追加

以下の参考書を元に、TopCoderの対策をしています。

今日は、動的計画法とメモ化再帰について勉強しました.

スポンサードリンク

動的計画法(Dynamic Programming)

対象となる問題を複数の部分問題に分割し、
部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ

分類

動的計画法には、トップダウン方式、ボトムアップ方式の二つがある. 以下のように呼ばれることが多い.

  • 再帰関数のメモ化 ・・・メモ化再帰、メモ化、トップダウン方式
  • 漸化式 + ループ ・・・動的計画法、分割統治法、ボトムアップ方式

トップダウン方式(メモ化再帰)

一度計算した結果を覚えておいて、 同じ計算をしようとしたときに記憶していた値を利用する.

再帰関数を利用することで、問題を解く.

ボトムアップ方式(漸化式)

漸化式を立てて、順々に漸化式を解いていく.

for文を回すことで、問題を解く.

問題

SRM413 Div1 Medium

動的計画法

まとめらる処理をまとめて、同じ計算を行わないようにする

途中経過をメモしておいて、次の計算で使うというのが動的計画法. ここでは、i を順に計算していく.

class InfiniteSequence2:
def calc(self, n, p, q, x, y):
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(1, n + 1):
nexta = i / p – x
nextb = i / q – y

if nexta <= 0: a = 1 else: a = dp[nexta] if nextb <= 0: b = 1 else: b = dp[nextb] dp[i] = a + b return dp[n] [/sourcecode]

深さ優先探索

トップダウンで探索をしていく.

class InfiniteSequence2:
def calc(self, n, p, q, x, y):
return self.dfs(n, p, q, x, y)

def dfs(self, n, p, q, x, y):
if n <= 0: return 1 return self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) [/sourcecode]

メモ化再帰

一度計算した点は覚えておいて、余計な計算をしないのがメモ化再帰.

class InfiniteSequence2:
def calc(self, n, p, q, x, y):
self.memo = {}
return self.dfs(n, p, q, x, y)

def dfs(self, n, p, q, x, y):
if n <= 0: return 1 if n in self.memo: return self.memo[n] self.memo[n] = self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) return self.memo[n] [/sourcecode]