【Python】白駿1003フィボナッチ

3854 ワード
アルゴリズム#アルゴリズム# 白駿 テキストリンク
リンク

白骏1003菲博纳奇


DP問題を解く経験が少ないため,この問題を再帰DPで解く.
memorizationを使うことしか覚えていないので、どうやって近づくか分からないので、他の人のコードを参考にしました.
最初は他人のコードを見ても流れがわからないので、そのままノートに流れを描き、理解に努めます.
私たちもDPをもっと解いてみましょう.

正しいコード

def fib(n):
    if n == 0 or n == 1:
        memo[n] = n
        return n
    elif memo[n] == 0:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

for _ in range(int(input())):

    memo = [0] * 41
    n = int(input())
    if n == 0:
        print('1 0')
    else:
        fib(n)
        print(memo[n-1], memo[n])

知るところ👨‍💻

  • 復帰は慣れていない.
  • Memoizaionのリストを最大値に初期化しておくと便利です.
  • 結果値をどこかに保存して、その値を入れて使えばいいのですが…
    • の練習も必要かもしれません
    02_03.グローバルフィルタとローカルフィルタ
    [アルゴリズム]白俊2789号-留学禁止