Dynamic Programming


ダイナミックプランニングとは


動的計画法には非常に簡単な原理がある。

  • 与えられた問題を複数のサブ問題に分けて解く,
  • .
  • サブ問題の解決方法と結びつけて、
  • 最終的な問題を解決します.
  • 動的プログラミングは、次の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];
    }