Dynamic Programming
6614 ワード
ダイナミックプランニングとは
動的計画法には非常に簡単な原理がある。
動的プログラミングは、次の2つの仮定が満たされる条件で使用できます。
いいですよ.
例
Recursion
function fib(n) {
if(n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
次の2つの例では、DP
の概念を使用します.Recursion + Memoization
function fibMemo(n, memo = []) {
if(memo[n] !== undefined) return memo[n];
// 이미 해결한 하위 문제인지 찾아본다
if(n <= 2) return 1;
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 없다면 재귀로 결과값을 도출하여 res 에 할당
memo[n] = res;
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
return res;
}
実際,演算を行ったのは左4個のみで,残りは左4個の値しか取らなかった.
Iteration + Tabulation
function fibTab(n) {
if(n <= 2) return 1;
let fibNum = [0, 1, 1];
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}
Reference
この問題について(Dynamic Programming), 我々は、より多くの情報をここで見つけました https://velog.io/@vagabondms/Dynamic-Programmingテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol