メモ化再帰

メモ化再帰の使い方

タグ メモ化再帰 reccursion

概要

  • dpの一つの実装形態の一つ
  • dfsで値を埋めていくイメージ
  • pythonであると、リストを使ったdpより少し遅い

具体例

house-robber

  • 連続する2つの値を取れない時
memo = {}
def rec(i, nums):
    if i >= len(nums):
        return 0
    if i in memo:
        return memo[i]
    # 配る
    ans = max(rec(i + 1, nums), rec(i + 2, nums) + nums[i])
    # 結果をメモ
    memo[i] = ans
    return ans

assert rec(0, [2,7,9,3,1]) == 12

参考