ダイナミックプログラミング
7152 ワード
ダイナミックプログラミング
ダイナミックプログラミングの条件
フィボナッチ数列
フィボナッチ数列は、動的プログラミングによって効率的に計算できる次の形式の数列です.
点火式とは、隣接するアイテム間の関係を指します.
フィボナッチ数列を点火式として表します.
フィボナッチ数列の計算プロセスは、次のように記述できます.
フィボナッチ数列の計算プロセスは、次のように記述できます.
フィボナッチ数列:Pythonソースコード
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))フィボナッチ数列の時間複雑度順序
フィボナッチ数列の有効な解法:動的プログラミング
注記構造
フィボナッチ数列:タワーダイナミックプログラミングソース(python)
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수 (Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건 (1 혹은 2일 떄 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 안흥 ㄴ문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))フィボナッチ数列:基準動的プログラミングソース(Python)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])Reference
この問題について(ダイナミックプログラミング), 我々は、より多くの情報をここで見つけました https://velog.io/@fredkeemhaus/다이나믹-프로그래밍-Dynamic-Programmingテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol