[白俊]1003号-(Python Python)-Memorization

994 ワード
白駿 DP テキストリンク
質問リンク:https://www.acmicpc.net/problem/1003


この問題は簡単なフィボナッチ数列の再帰関数を用いた.
再帰関数の欠点値が大きくなると、演算が多すぎます.
解決したメモを利用して問題を解くのがこの問題の目的だ.
注記転送は、繰り返し呼び出しを補う方法です.
その名の通り,関数の結果値を他の資料構造に記入する.

コメント作成を使用すると、重複呼び出しを減らすことができることは、画像から容易にわかります.
import sys
read = sys.stdin.readline

dp ={
  0 : 0,
  1 : 1,
  2 : 1
}

def f(n):
  if n not in dp:
    dp[n] = f(n - 1) + f(n - 2)
  return dp[n]

t = int(read())
for _ in range(t):
  num = int(read())
  if not num:
    print('1 0')
  else:
    f(num)
    print(dp[num - 1], dp[num])
今回のフィボナッチ数列問題は簡単だが.
DP問題の特徴は,注釈再構成が容易であることである.
回帰ルールを探すのは
肝心なのは帰納法を探すことだ.
media query
[白俊]1949号:優秀村