[アルゴリズム]動的プログラミング

アルゴリズムの学習が最も困難なのは,動的プログラミング,DPである.高校生の頃も点火式の設置が一番苦手でしたが...やはり難しいですね.

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

以前の範囲の値を利用して特定の範囲の値

を求める方法

大きな問題を小さな問題に分けるための問題のうち

Memoization-

の繰り返し計算を回避するために、以前の値を保存します.

フィボナッチ数列再帰関数vs動的計画法

単純再帰関数

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

ダイナミックプランニングの活用

int fibonacci(int n){
	if (n<=1) return n;
	if (dp[n]) return dp[n];
	return dp[n]=fiboancci(n-1)+fibonacci(n-2)

ダイナミックプランニング法はnが大きい場合にタイムアウトしません

Top-down vs Bottom-up

上に記述したコード方式はnから探索を開始するTop-Down方式である.
Boottom-upは0から探索を開始し,既知の小さな問題から必要な場所まで探索した.(top-downよりも速い)
Bottom-up

dp[0]=1;
dp[1]=1;
for (int i=2; i<=N; i++) {
	dp[i]=dp[i-1]+dp[i-2];

解法

以前の値と現在の値との関係(表を使用)

について説明します.

点火式確立

例

百準11053成長最長の部分数列

に近づく💡

現在のインデックスは、前のインデックスの最長長

に参照することができる.

は、インデックスで終わるインクリメンタル配列の中で最も長い

にナビゲートする.

コード#コード#💻

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
  //dp 배열을 1로 초기화 (최소 길이가 1이므로)
	vector<int> dp(N+1,1);
	vector<int> A(N+1);
	int answer = 1;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
  //현재 인덱스부터 그 이전 인덱스와 비교해서 dp값 갱신
	for (int i = 2; i <= N; i++) {
		for (int j = i-1; j >= 1; j--) {
			if (A[i] > A[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		answer = max(answer, dp[i]);
	}
	cout << answer;
}

課題

標準11727:2 xnタイル2

に近づく💡

、長さ固定、横長可変

充填のタイルの種類は12,21,2*2なので、これまでに作られたタイルがどのようなタイルで横道を完成するのかを考えると

となります

この問題を解くときは、矩形を直接数えます.dp解くたびにどうやって解くかわかるようですが、点火式で立つのが一番難しい感じです

長方形を描き続け、考えてみれば横に貼ることができるのは横長1,2なので、n-1の横長+1*2タイル1個の場合とn-2の横長と横長2が完成する場合を合わせていけばいいと思います.2つ目のケースは2つあるので、点火式を作れば
dp[n]=dp[n-1]+ 2*dp[n-2]

コード#コード#💻

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int>dp(N + 1);
	dp[1] = 1;
	dp[2] = 3;
	for (int i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + 2 * dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[N];
}

dpのコードは簡単ですが、思いつく過程は難しいです...🥺 dpは解き続ける必要があります