この文章はBaekjoon、フィボナッチ数の各種の方法を求めますの投稿を学ぶために書かれたものです.投稿はC/C++で書かれているので、筆者のエンコードテストの主な言語Pythonに変換してみました.

手順1。よびだし

白駿10870。フィボナッチ数5を解くことができ、この問題ではn <= 20である.

n = int(input())

def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(n))

時間の複雑さ:O(2^N)はほぼ2倍に増加します.

手順2。コメント作成（DP）

白駿2747。フィボナッチ数を解くことができ、この問題ではn <= 45である.

n = int(input())
dp = [0] * (45+1)

def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if dp[n]:
        return dp[n]
    dp[n] = fibo(n-1) + fibo(n-2)
    return dp[n]

print(fibo(n))

時間複雑度:O(N)実際のdpは1回のみ計算されます.残りは使ってください.

手順3。分類（DP）

白駿2748。フィボナッチ数2を解くことができ、この問題ではn <= 90である.

n = int(input())
dp = [0] * (90+1)
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

元の投稿では、n値が大きくなるにつれて、データ型をlong longに変更する必要がありますが、Cとは異なり、PythonはBigIntもサポートしているので、他のデータ型を宣言する必要はありません.

の第2段階および第3段階の時間的複雑さはO(N)であるため、実際には、任意のアルゴリズムを用いて通過することができる.

メモ帳とグラフはDP(Dynamic Programming)の代表的な2つの技術である.
コードから直感的に理解できるように、注釈は現在、既存の下から上への再帰コード(第1段階)では、繰り返し計算値の下から上への動的プログラミング技術のみを除去し、時間ストリームはfor文を用いて小さな値から計算を開始し、上への下から上への動的プログラミング技術である.

手順4。ピサノ周期

白駿2749。フィボナッチ数3を解くことができ、この問題ではn <= 1,000,000,000,000,000,000であるが、1,000,000으로 나눈 나머지の条件がある.

n = int(input())
dp = [0] * (1500000)
dp[1] = 1

for i in range(2, 1500000):
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= 1000000

print(dp[n%1500000])

フィボナッチ数をKで割った残りの部分には常に周期がある.これを「光周期」(Pisano Period)と呼ぶ.나머지 = 10^kの場合、k > 2の場合、周期はいつも15 × 10^(k-1)です.これを知らない場合でも、サイクルを求めるコードを使用して問題を解決できます.
上記の問題にピサノサイクルを適用すると、以下のようになります.

フィボナッチ数を10^6で割った後、周期は15*(10^5) = 1500000であった.

ライフサイクルの長さは15万です.N번째 피보나치 수 % 1000000==N%1500000번째 피보나치 수 % 1000000.

手順5。マトリックスと分割征服

残りの部分が大きくなると、dp配列のlenも大きくなるので、ピサノ周期も限られています.
白駿11444。フィボナッチ数6を解くことができ、この問題は上記の問題と同じであるが、n <= 1,000,000,000,000,000,000の条件下では、上記dpアレイの1000倍長いアレイを宣言しなければならず、メモリが限られているため、擬似周期は使用できない.

このような状況が発生したプロセスは以下の通りである.

1)反復征服による分割

原帖の符号化方式はこの方式である.

import copy

n = int(input())

def matrix_mul(A, B):
    C = [[0] * len(B[0]) for _ in range(len(A))]
    for i in range(len(C)):
        for j in range(len(C[0])):
            for k in range(len(A[0])):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= 1_000_000_007
    return C

if n == 0:
    print(0)
    exit()

rv = [[1, 0], [0, 1]]
a = [[1, 1], [1, 0]]
while n:
    if n%2 == 1:
        rv = matrix_mul(rv, a)
    a = matrix_mul(a, a)
    n //= 2

print(rv[0][1])

2）再帰分割征服

分割征服は通常再帰的に組織される.
可読性を向上させるコードを再帰的に作成してみましょう.

# "분할 정복을 이용한 거듭제곱"의 의미
# 2**10 == 2**5 * 2**5
# 2**11 == 2**5 * 2**5 * 2 느낌

n = int(input())

def mmul(A, B):
    C = [[0] * len(B[0]) for _ in range(len(A))]
    for i in range(len(C)):
        for j in range(len(C[0])):
            for k in range(len(A[0])):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= 1_000_000_007
    return C

if n == 0:
    print(0)
    exit()

def mpow(a, n):
    if n == 1:
        return a
    a = mpow(a, n//2)
    a = mmul(a, a)
    if n%2 == 1:
        return mmul(a, [[1, 1], [1, 0]])
    return a

rv = mpow([[1, 1], [1, 0]], n)
print(rv[0][1])