プログラミングの過程で、規模の大きい問題を解決したり処理したりする必要がある場合があります.
この場合,問題をより効率的に処理するために,動的プログラミングが用いられる.

📒Dynamic Programming(DP)

Synnamin Programmingとは?

複雑な大きな問題を複数の簡単な小さな問題に分解する.

方法

大きくて複雑な問題をいくつかの簡単な小さな問題に分けます.

の小さな問題から、大きな問題を解決する方法で解決します.(BOTTOM-UP)

小さな問題の結果を記憶し、大きな問題を解き、必要に応じて書き出す.

の問題を一度解けば、二度と解けない.

📌 BOTTOM-UP

小さな問題から順に解く方法で、複文を使うことが多い.

インプリメンテーション

(Fibonacci数列)

int fibonacci(int n)
{
	int fir=0;
    int sec=1;
    for(int i=2; i<=n; i++){
    	next=fir+sec;
        fir=sec;
        sec=next;
    }
    return next;
}

📌 TOP-DOWN

BOTTOM-UP法とは逆の方法で再帰関数で解く場合が多い.大問題を解くには小問題が必要で、その時は小問題を解く.
動的プログラミング方法ではありません.

インプリメンテーション

(Fibonacci数列)

int fibonacci(int n)
{
	if(n==0){
    	return 0;
    }
    else if(n==1){
    	return 1;
    }
    else{
    	return fibonacci(int n-2) + fibonacci(n-1);
    }
    return -1;					//오류의 경우
}

条件

小さな問題が繰り返される場合

.
-これは分割征服との違いです.分割征服には小さな問題の繰り返しはない.

のような質問では、答えはいつも同じです.
-1つの問題は1回のみ解決されます.

📒Memoization

「オブジェクト化」とは?

同じ計算を繰り返す場合は、以前に計算した値をメモリに格納し、繰り返し実行を排除し、実行速度を速めます.
ダイナミックプログラミングでは、小さな問題の答えをメモリに格納して再使用することで、プログラムの実行速度を速めます.

インプリメンテーション

(Fibonacci数列)

int fibonacci(int n)
{
	int arr[1001];
    arr[0] = 0;
    arr[1] = 1;
    
    for(int i=2; i<=n; i++){
    	arr[i] = arr[i-2] + arr[i-1];
    }
    
    return arr[n];
}

ダイナミックプログラミングとメディア化を利用して大きな問題を解決することができます.