[アルゴリズム]動的計画法動的計画,DP

🌟 動的計画法動的計画,DP
定義:

複雑な問題を複数の単純な問題に分解する方法

問題をシンプル化し、再利用可能な構造を使用して問題を解決する方法
シンプル化→点火→再帰構造→ソリューション

方法:

問題全体を小さな問題に簡略化

再帰構造を利用した点火式の作成

小さな問題で問題全体を解決する

注記アニメーション:
定義:
動的計画で使用されるポリシーを使用して関数の値を計算し、計算値を配列に格納します.
機能:
必要なときに呼び出さずに、値をすばやく取得できます.
例:
フィボナッチ数列

再帰関数を用いたフィボナッチ関数

int fibo(int n){
	if(n < 2)
		return n;
    return fibo(n-1) + fibo(n-2);
}

動的計画法を用いたフィボナッチ関数

int fibo(int n){
	if(n < 2)
    	return n;
    if(memo[n] != 0){
    	return memo[n];
    }
    else{
    	memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

再帰関数を使用するコードでは、
fibo(10)の値が求められると、f(10)の値を求めるには、fibo(9)からfibo(1)の値を求めなければならない
f(n) = f(n-1) + f(n-2), f(n-1) = f(n-2) + f(n-3)...
しかし、ダイナミックプランニング法を利用すれば
fibo(10)の値を求めて、fibo(9)、fibo(8)の値だけを必要とします
f(n) = f(n-1) + f(n-2)
配列に以前の値が格納されている場合、重複する値が発生した場合は、再評価する必要はありません.
そしてあなたが貯めたお金を計算します.
これにより、関数の呼び出し回数が減少し、実行効率が向上します.
私はあなたの時間を無駄にしません.
I'll write something that won't waste your time.