Dynamic Programming

ダイナミックプログラムとは?
💡最も簡単なのは点火式を求め、計算を繰り返すことです.
以前に使用した値を再利用することは容易であると理解される.
フィボナッチ数列は最も容易で最も速く理解できる例だと思います.
フィボナッチ数列とは1、1、2、3、5、8、13…前の2つの項目に加算された数列のようです.
従って、f(n)=f(n−1)+f(n−2)計算式を用いて求めることができる.

// 재귀함수 이용(recursive)
public static int fibo(int n){
	if(n == 1 || n ==0 ){
    	return 1;
    }
    return fibo(n-1)+fibo(n-2);
}

上のような簡単な計算なら大丈夫だと思いますが、
🤦‍♀️ fibo(10)関数を再帰的に呼び出すと、数値が大きくなるにつれてスタックオーバーフローが発生します.
これらの問題は、ダイナミックProgramingテクノロジーで解決できます.
🙆‍♀️ fibo()関数を呼び出す回数を最小限に抑え、計算済みであればコードを変更して値をロードして再使用します.(これは理解を助けるために書かれた非常に簡単なコードです...)

// DP를 이용한 피보나치 수열
public static int[] fibo = new int[10];			// dp를 사용하기 위해 int[] 배열을 선언

public static int fibo(int n){
    fibo[0] = 1;
    fibo[1] = 1;
    for(int i=2; i<=n; i++){
    	// 식을 이용하여, 이전에 사용했던 계산식을 재활용한다.
        // 이것을 memoization이라고 할수 있다.
    	fibo[i] = fibo[i-1] + fibo[i-2];
    }
    return fibo[n];
}

👀では、ダイナミックProgramingは無条件呼び出し再帰関数よりも優れていますか?
1.時間複雑度:DPO(n^2)<再帰O(2^n)
時間の複雑さから見ると、DPはずっと速い.
2.空間複雑度:DP>再帰
DPはメモリ領域を占有する.
memorizationテクノロジーを使用しているため、計算した値を保存し、必要に応じて計算を繰り返すことなく呼び出すことができます.上記の簡単な例だけを見ると、int[]のようにどこかに値を格納する必要があります.
では、DPについてもっと詳しく説明しましょう.
DPアルゴリズムタイプ
マルチアウトレットアルゴリズム
1つの頂点から別のすべての頂点への最短パスを求めるアルゴリズム
Floyd Warshallアルゴリズム
すべての最短経路のアルゴリズムを求めます
すべての頂点からすべての頂点への最短パス.
詳細は▶▶▶Floyd Warshallアルゴリズム
DPメソッド
フィボナッチ数列で説明を続けます.
アノテーション
DP=コメントは今回の操作ではありません.
しかし、覚書の現在の概念は分かりやすいようなので、一緒に説明します.
これは、計算された値を破棄せずに保存することを意味します.
計算した値を保存し、必要に応じて呼び出します.
このように格納される配列を「キャッシュ」と呼び、中間記憶される表現を「キャッシュ」と呼ぶ.
TopDown
これは再帰関数です.
fibo(10)を求めると、fibo(9)、ffibo(8)の大数から再帰呼び出しを継続する方法を示す.

public int[10] fibo = {0,};		// 배열을 0으로 모두 초기화

public class int fibonachi(int n){
	if(n <2){		// fibo[0] , fibo[1] = 1;
    	return 1;
    }
    
    if( fibo[n] == 0){
    	fibo[n] = fibo[n-1] + fibo[n-2];
    }
    return fibo[n];
}

Bottom up
デフォルト値を使用して特定の値を計算する方法.
fibo(1)からfibo(10)まで順次上昇します.DP를 이용한 피보나치 수열ソースコードを参照してください.
[参考ブログ]
[アルゴリズム]ダイナミックプランニング(Dynamic Programming)-1
12.動的計画法
フロリダ州とシェルアルゴリズム