慕課での学習ノートと例題コードを記録します。
一。再帰から動的計画法への一般的な変換方法#
再帰関数が n 個の引数を持つ場合、n 次元の配列を定義します。配列のインデックスは再帰関数の引数の値の範囲です。
これにより、境界値から始めて配列を徐々に埋めることができ、再帰関数の値を計算する逆のプロセスに相当します。例：例題 1 数字三角形
二。動的計画法による問題解決の一般的な考え方#
1. 元の問題を子問題に分解する#
元の問題をいくつかの子問題に分解します。元の問題と形式が同じまたは類似しているが、規模が小さいだけです。
子問題がすべて解決されれば、元の問題も解決されます。
子問題の解が一度求められると保存されるため、各子問題は一度だけ解決すればよいです。
2. 状態を定義する#
状態：子問題に関連する各変数の値の組を状態と呼びます。1 つの状態は 1 つ以上の子問題に対応します。
値：ある状態の値とは、その状態に対応する子問題の解です。
時間計算量：全体の問題の時間計算量は状態の数と各状態に必要な時間の積です。
保存：K 個の整数型変数が 1 つの状態を構成でき、値の範囲がそれぞれ N1,N2,…,Nk である場合、K 次元の配列 array [N1][N2]…[Nk] を使用して各状態の「値」を保存できます。この値は整数や浮動小数点数である必要はなく、構造体で表される場合もあるため、array は構造体配列である可能性があります。
3. いくつかの初期状態（境界状態）の値を定義する#
4. 状態遷移方程式を定義する#
状態とは何か、またその状態の値を定義した後、異なる状態間の遷移方法を見つける必要があります。
つまり、1 つまたは複数の既知の値を持つ状態から別の状態の値を導き出す方法（「みんなが私のために」再帰型）です。状態の遷移は再帰公式で表すことができ、この再帰公式は「状態遷移方程式」とも呼ばれます。
三。動的計画法で解決できる問題の特徴#
1) 問題が最適部分構造の性質を持つ#
最適部分構造の性質：もし問題の最適解に含まれる子問題の解も最適であるなら、その性質を持つと呼びます。
2) 後悔性がない#
現在のいくつかの状態値が決定されると、その後のプロセスの変化はこれらの状態の値にのみ関連し、以前にどの手段を取ったかやどの経路を通ったかには関係ありません。
四。例題#
例題 1. 数字三角形#
題意
: n 行の数字からなる数字三角形が次の図のように与えられます。三角形の頂点から底までの経路を設計し、その経路を通る数字の合計が最大になるようにします。
n 行の数字からなる数字三角形が与えられた場合、三角形の頂点から底までの経路を通る数字の合計の最大値を計算します。
入力データの第 1 行は数字三角形の行数 n で、1≤n≤100 です。次の n 行は数字三角形の各行の数字です。すべての数字は 0..99 の範囲です。
出力データは 1 つの整数で、計算された最大値を示します。
示例入力
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
示例出力
30
コード 1 メモリ再帰型動的計画法プログラム
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//再帰を使用するとタイムアウトするため、重複計算が多すぎます
//そのため、各再帰の結果を配列に保存します
//これをメモリ再帰型動的計画法プログラムと呼びます
int D[MAX][MAX];//D[r][j]は第r行第j個の数字を表します（r,jは1からカウント）
int maxSum[MAX][MAX];//D(r,j)から底辺までの各経路の中で、最適経路の数字の合計
int n;
int MaxSum(int i, int j) {
if (maxSum[i][j] != -1)
return maxSum[i][j];//maxSumの値が計算されている場合
if (i == n)
maxSum[i][j] = D[i][j];
else {
int x = MaxSum(i+1, j);
int y = MaxSum(i+1, j+1);
maxSum[i][j] = max(x, y) + D[i][j];
}
return maxSum[i][j];
}
int main(){
int i, j;
cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
}
cout << MaxSum(1, 1) << endl;
return 0;
}
コード 2 ループ再帰式動的計画法
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//ループ再帰式動的計画法
int D[MAX][MAX];//D[r][j]は第r行第j個の数字を表します（r,jは1からカウント）
int maxSum[MAX][MAX];//D(r,j)から底辺までの各経路の中で、最適経路の数字の合計
int n;
int main(){
int i, j;
cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
}
for (i = 1; i <= n; i++)
maxSum[n][i] = D[n][i];
for (i = n-1; i >= 1; i--) {
for (j = 1; j <= i; j++) {
maxSum[i][j] =
max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
}
}
cout << maxSum[1][1] << endl;
return 0;
}
例題 2. 神秘のポケット#
題意
神秘のポケットがあり、全体の容積は 40 です。このポケットを使っていくつかの物品を作り出すことができ、これらの物品の総容積は 40 でなければなりません。John は現在 n 個の欲しい物品を持っており、それぞれの物品の容積は a1，a2……an です。John はこれらの物品の中からいくつかを選ぶことができ、選ばれた物体の総容積が 40 であれば、この神秘のポケットを使って John はこれらの物品を得ることができます。現在の問題は、John が物品を選ぶ方法が何通りあるかです。
入力出力
入力:
3
20
20
20
出力:
3
コード
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[30]; int N;
int Ways[40][30];//Ways[i][j]はj種類の物品から体積iを作る方法の数を表します
int main() {
cin >> N;
memset(Ways, 0, sizeof(Ways));
for (int i = 1; i <= N; ++i) {
cin >> a[i]; Ways[0][i] = 1;
}
Ways[0][0] = 1;
for (int w = 1; w <= 40; w++) {
for (int k = 1; k <= N; k++) {
Ways[w][k] = Ways[w][k-1];
if (w-a[k] >= 0)
Ways[w][k] += Ways[w-a[k]][k-1];
}
}
cout << Ways[40][N];
return 0;
}
例題 3. 最長共通部分列#
題意
2 つの文字列を与え、最長の共通部分列の長さを求めます。
入力出力
入力:
abcfbc abfcab
programming contest
abcd mnp
出力:
4
2
0
コード
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1001][1001];
/*考え方:dp(i,j)はs1の左側i文字から形成される部分列
とs2の左側j文字から形成される部分列の最長共通部分列の長さを表します
dp(n,0) = 0, dp(0,n) = 0;
if (s1[i-1] == s2[j-1]) dp(i,j) = dp(i-1,j-1) + 1;
else dp(i, j) = max(dp(i,j-1), dp(i-1,j));*/
int main() {
string s1, s2;
cin >> s1 >> s2;
int len1 = s1.length();
int len2 = s2.length();
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <=len2; j++) {
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
cout << dp[len1][len2] << endl;
return 0;
}
例題 4. 最長上昇部分列#
題意
入力の最初の行は列の長さ N、2 行目は N 個の整数です。
最長上昇部分列の長さを出力します。
入力出力
入力例:
7
1 7 3 5 9 4 8
出力例:
4
コード
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
/*考え方:akを終点とする最長上昇部分列の長さを求めることに分解します。maxLen(k)はakを終点とする最長上昇部分列の長さを表します。
akの左側でaiがakより小さい最大の長さの最長上昇部分列の長さ+1です。
akの左側の任意の終点がakより小さい部分列にakを加えることで、より長い上昇部分列を形成できます。*/
int a[maxn]; int maxLen[maxn];
int main() {
int N, ans = -1; cin >> N;
for (int i = 1; i <= N; i++) {
cin >> a[i]; maxLen[i] = 1;
}
for (int i = 2; i <= N; i++) {
//毎回第i個の数を終点とする最長上昇部分列の長さを求めます
for(int j = 1; j < i; j++) {
//第j個の数を終点とする最長上昇部分列
if (a[j] < a[i]) {
maxLen[i] = max(maxLen[i], maxLen[j]+1);
}
}
}
for (int i = 1; i <= N; i++) {
if(maxLen[i] > ans) ans = maxLen[i];
}
cout << ans << endl;
return 0;
}
//時間計算量O(N^2)
慕課プログラミングとアルゴリズム（二）動的計画法 ppt からの転載