DPダイナミックプログラミング

DP欄

大きな問題を小さな問題に分けるアルゴリズム.
方式は分割征服と同じであるが,分割征服は1回の計算の一部の問題のみを書き,使用しない.ただし、ダイナミックプログラミングでは、計算の一部が保持され、必要に応じて使用され続けます.
従来の方法と比較して,局所問題の繰返しと最適局所構造をもつアルゴリズムを用いて,より少ない時間で解いた.

さぎょうモード

救いたい大問題は小問題△点火式を作る.

最小部分の問題を解決して値を保存します.備忘録様式

完成した問題の値を利用して、より大きな問題の答えを逐次求める.

最大の問題を解くまで繰り返す.
☆大切なのは何を保存するかを決めることです.

ダイナミックプランニングメソッド

1.Bootton-Upモード:繰り返し文の使用

下から上へのアプローチ.
局所的な問題から始め、大きな問題を徐々に解決する方法です.
ex)
整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.
仮に4分を1、2、3とする

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

実行できるはずです.全部で7つのケースがあります
1であれば、1つのケースがあります.
インスタントラーメン2種
三則四則
ラーメン4個について
5であれば13のケースが発生します.
ここから導出可能d[n] = d[n-1]+d[n-2]+d[n-3]このような直観的な小解を求めると,それを利用してより大きな問題を解決することができる.
この方法をBottom−up方式と呼ぶ.
ex2)

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {

    for(int i = 3; i <=n; i++){
      memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
  }

2.Top-Down方式：再帰関数の使用

これは上から下へ近づく方法です.
大問題から局所問題まで,再帰呼び出しを用いて解く方法である.
例文と「前の問題」、翻訳メモリ
Boottom-upを使用する場合、
d[7]が要求される場合、d[6]d[5]d[4]を知る必要がある
d[6]を得るには、d[5]d[4]d[3]を知る必要があります.

一つ一つ解くとd[5]とd[4]が重なる作業が繰り返され,時間の複雑さの浪費をもたらす.

求めた値を記録し,不要な再帰呼び出しを防止するアノテーション転送操作を行う.

ex2)

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
int memo[101];

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
int fib(int n)
  {
    if (memo[n] != 0) 
      return memo[n];

    memo[n] = fib(n-1) + fib(n-2);

    return memo[n];
  }

4.動的計画法の運用方法

実際の符号化試験において,DPを用いて問題を解く方法

質問の答えを文で表す.

文章中の変数数に応じて、コメント用のキャッシュアレイを生成する.

問題を部分的な問題に分け、点和式を求めることで問題を関数として表す.

運用

Top-Down의 경우 재귀 함수Bottom-Up의 경우 for문解答を導き出す.

階調アルゴリズムvsダイナミックプランニング法

比較した貪欲アルゴリズム(グリッドアルゴリズム)と比較し,その利点を問題に適用すべきである.
動的計画法:すべての方法を逐一研究し、最適解の方法を探し出す.

常に最適年が検出されるが、時間がかかる.

🧐 グリディ:すべての解を求めず、一瞬ごとに最適な解を見つけるアルゴリズムです.

ベストイヤーではないかもしれませんが、短い時間の長さを比較しましょう.

出所https://happy-time-daily-blog.tistory.com/47