動的計画法

本日もやっていきます
問題 1:　最大和問題
n個の整数 a[0],a[1],…,a[n−1]が与えられる。これらの整数から何個かの整数を選んで総和をとったときの、総和の最大値を求めよ。また、何も選ばない場合の総和は 0 であるものとする。

【制約】
・1≤n≤10000
・−1000≤a[i]≤1000

```
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[10010];
int dp[10010];
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		dp[i + 1] = max(dp[i], dp[i] + a[i]);
	}
	cout << dp[n];
	return 0;
}

```
漸化式って感じ

問題２
n個の品物があり、i番目の品物のそれぞれ重さと価値が weight[i],value[i]となっている (i=0,1,...,n−1)。
これらの品物から重さの総和が Wを超えないように選んだときの、価値の総和の最大値を求めよ。

【制約】
・1≤n≤100
・weight[i],value[i]は整数
・1≤weight[i],value[i]≤1000
・1≤W≤10000

ナップサック問題とかいう超有名な問題らしい
dp[i+1] := i番目までの中から重さがwを超えないように選んだ時の価値の総和の最大値とするとdp[i+1]を考えるときにdp[i]に対して品物(weight[i],value[i])を加えるか否かを考えるわけだけど加えた時に重さがwを超えてしまうのかどうかがわからないという問題が起こる。だから
dp[i+1][w] := i番目までの品物の中から重さがwを超えないように選んだ時の価値の総和の最大値
という風にする
dp[i][w]の値が求まっていることを前提にしてdp[i+1][w]を考える。
＜DP漸化式＞
[w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])※w>=weight[i]の時
    dp[i][w]
※w<weight[i]の時
＜DP初期条件＞
dp[0][w] = 0 (w=0,1,,,,,W)

```
#include<iostream>
#include<climits>
#include<algorithm>
using namespace std;
int n,W;
int weight[110], value[110];
int dp[110][10010];
int main(){
	cin >> n >> W;
	for (int i = 0; i < n; ++i)cin >> value[i] >> weight[i];
	//DP初期条件:dp[0][w]
	for (int w = 0; w <= W; ++w)dp[0][w]=0;

	for (int i = 0; i < n; ++i) {
		for (int w = 0; w <= W; ++w) {
			if (w >= weight[i])dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
			else dp[i + 1][w] = dp[i][w];
		}
	}
	cout << dp[n][W];
	return 0;
}
```

問題 3:　部分和問題　
n個の正の整数 a[0],a[1],…,a[n−1]と正の整数Aが与えられる。これらの整数から何個かの整数を選んで総和がAになるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤n≤100
・1≤a[i]≤1000
・1≤A≤10000

[解法]
dp[i+1][j]:=i番目までの整数の中からいくつか選んで総和をjとすることが可能かどうか(bool値）
として、dp[i][j]を使ってdp[i+1][j]の値を更新することを考える
dp[i+1][j]の値を求める方法
.整数a[i]を選ぶ場合(j>=a[i]の場合のみ)
dp[i][j-a[i]]がtrueならdp[i+1][j]もtrue
.整数a[i]を選ばない場合
dp[i][j]がtrueならdp[i+1][j]もtrue
＜DP漸化式＞
dp[i+1][j] = dp[i][j-a[i]] | dp[i][j]※(j >= a[i])
             dp[i][j] ※(j<a[i])

＜DP初期条件＞
dp[0][j] = true (j=0)
           false (j!=0)
|はor演算子である。

```
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	int n,a[100], A;
	bool dp[100][10010];
	cin >> n >> A;
	for (int i = 0; i < n; i++)cin >> a[i];
	memset(dp,0,sizeof(dp));//いったん全部falseに
        dp[0][0] =  true;//dp[0][0]だけtrueに
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= A; ++j) {
			if(j<a[i])dp[i + 1][j] = dp[i][j];
			else dp[i + 1][j] = dp[i][j- a[i]] | dp[i][j];
		}
	}

	if (dp[n][A])cout << "yes";
	else cout << "no";
	return 0;
}
```
これであってるのかなとりあえず動いたから大丈夫そうではあるけど。｜はorを示していてbool値ではtrue|falseだとtrueになるってことか普通に文法が未熟すぎる。このmemset(a,b,c)でaはメモリのポインタ。bはセットする値。cはセットするサイズ。これを使うためにcstringaをincludeしてるのかな？

問題４
n個の正の整数 a[0],a[1],…,a[n−1]と正の整数Aが与えられる。これらの整数から何個かの整数を選んで総和がAになるようにする方法が何通りあるかを求めよ。ただし、答えがとても大きくなる可能性があるので、1,000,000,009 で割った余りで出力せよ。

【制約】
・1≤n≤100
・1≤a[i]≤1000
・1≤A≤10000

n=4
a=(4,1,1,1)
A=5
　答え: 3 ((4, 1), (4, 1), (4, 1) の 3 通りがあります。同じ 1 でも index が違うものは異なる組合わせとみなします)

部分和問題に少し変更を付け加える
dp[i+1][j] :=i番目までの整数の中からいくつかを選んで総和をjとする場合の数として
＜DP漸化式＞
dp[i+1][j] = dp[i][j-a[i]]+dp[i][j] if (j>=a[i])
           　　　　　= dp[i][j] if (j<a[i])と書ける
＜DP初期条件＞
dp[0][j] = 1  if(j=0)
         　　　　= 0  if(j!=0)

```
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 1000000009;
int n, a[1010], A;
int dp[110][10010];
int main() {
	cin >> n >> A;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= A; j++) {
			if (j >= a[i])(dp[i + 1][j] = dp[i][j] + dp[i][j - a[i]]) %= MOD;
			else (dp[i + 1][j] = dp[i][j]) %= MOD;
		}
	}
	cout << dp[n][A];

	return 0;
}
```

表記法についてなんかしっくりくるような来ないようなという感じ、、
(dp[i + 1][j] = dp[i][j] + dp[i][j - a[i]]) %= MODだとエラーにならないけどdp[i + 1][j] = （dp[i][j] + dp[i][j - a[i]]) %= MODだとエラーになる。まだこのへんがしっくりこないな

問題 5:　最小個数部分和問題　
n個の正の整数 a[0],a[1],…,a[n−1]と正の整数Aが与えられる。これらの整数から何個かの整数を選んで総和をAにする方法をすべて考えた時、選ぶ整数の個数の最小値を求めよ。Aにすることができない場合は -1 と出力せよ。

【制約】
・1≤n≤100
・1≤a[i]≤1000
・1≤A≤10000
[解法]
dp[i+1][j]:= i番目までの整数の中からいくつかの整数を選んで総和をｊとする方法をすべて考えた時の、選んだ整数の個数の最小値とするとdp[i+1][j]の値を求めるには、以下の二つの場合のminimumをとる。
.a[i]を選ぶ場合(j>=a[i]の場合のみ)
  dp[i][j-a[i]]+1
.a[i]を選ばない場合
　dp[i][j]
まとめると
<DP漸化式>
dp[i+1][j]=min(dp[i][j-a[i]]+1,dp[i][j])(j>=a[i])
dp[i+1][j]=dp[i][j] (j < a[i]

<DP初期条件>
dp[0][j] = 0(j=0)
         = ∞(j!=0)
最小値を求めるときに解なしだと、coutで出力すると∞になるっぽい

```
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 1 << 29;
int n, A;
int a[110];
int dp[110][10010];
int main() {
	cin >> n >> A;
	for (int i = 0; i < n; i++)cin >> a[i];
		for (int j = 0; j < 10010; j++) {
			dp[0][j] = INF;
		}
	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= A; ++j) {
			if (j >= a[i])dp[i + 1][j] = min(dp[i][j], dp[i][j - a[i]+ 1);
			else dp[i + 1][j] = dp[i][j];
		}
	}
	if (dp[n][A] < INF) cout << dp[n][A];
	else cout << -1;
}
```
1<<29は２の29乗を表しているらしい

問題 6:　K個以内部分和問題
n個の正の整数 a[0],a[1],…,a[n−1]と正の整数Aが与えられる。これらの整数からK個以内の整数を選んで総和がAになるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤K≤n≤500
・1≤a[i]≤1000
・1≤A≤10000

問題３にK個以内という制約が加わった。3と同じく
dp[i+1][j]:=i番目までの整数の中からいくつか選んで総和をjとすることが可能かどうか
とするとk個超えたかどうかわからないそこで
dp[i+1][j][k]:=i番目の整数の中からk個の整数を選んで足した総和をjとすることができるかどうか
とすれば確かにこの問題を解くことができるが計算量が多すぎて処理しきれない時がある。だから
dp[i+1][j] := i番目までの整数の中からいくつかの整数を選んで総和をjとする方法を考えた時の選んだ整数の個数の最小値として
・dp[n][A]<=Kならば"YES"
・dp[n][A]>Kならば"NO"
とすれば解ける

問題 7:　個数制限付き部分和問題
n種類の正の整数 a[0],a[1],…,a[n−1]がそれぞれ m[i]個ずつある。また、正の整数 Aが与えられる。これらの整数からいくつか選んで総和が Aになるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤n≤500
・1≤a[i],m[i]≤10000
・1≤A≤10000

dp[i+1][j]:=i番目まででjが作れるか
i番目まででjを作るためには、i-1番目まででj,j-a[i],,,,j-m[i]×a[i]のどれかが作られている必要があり、したがって漸化式は、
dp[i+1][j]=(0<=k<=m[i]かつk×a[i]<=jでdp[i][j-k×a[i]]が真となるkが存在するとすればよいが、そうするとまたしても計算量が大きくなってしまう。よって

dp[i+1][j]:=i番目まででjを作る際に余る最大のi番目の個数（作れない場合は-1)
と定義してみると、i-1番目まででjを作れるならi番目をm[i]個残してjを作ることができるまたi番目まででj-a[i]を作る際にi番目をk(>0)個残すことができるならば、i番目をk-1個残してjを作ることができます。従って漸化式は
dp[i+1][j] =   m[i](dp[i][j]>=0
dp[i+1][j] =  -1(j<a[i]またはdp[i+1][j-a[i]<=0)
dp[i+1][j] =   dp[i+1][j-a[i]]-1(それ以外

となる。最終的な答えはdp[n][k]>=0であるかどうかを調べることで得られる

配列の再利用をして

```
#include<iostream>
#include<algorithm>
using namespace std;

int dp[100010];
int n;
int K;
int a[100010];
int m[100010];
int main() {
	cin >> n >> K;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int j = 0; j < n; j++)
		cin >> m[j];
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= K; j++) {
			if (dp[I][j] >= 0) {
				dp[I+1][j] = m[i];
			}
			else if (j < a[i] || dp[j - a[i]] <= 0) {
				dp[j] = -1;
			}
			else {
				dp[I+1][j] = dp[I][j - a[i]] - 1;
			}
		}
	}
	if (dp[i][K] >= 0)
		cout << "yes";
	else
		cout << "no";
	return 0;
}

```
複雑になってきたな
問題 8:　最長共通部分列 (LCS) 問題
2つの文字列S,Tが与えられる。"abcde" といった文字列の部分文字列とは、"a", "ad", "abe" といったように、文字列から文字を幾つか抜き出して順に繋げてできる文字列のことを言うものとする。このとき、SとTの共通の部分文字列となる文字列の長さの最大値を求めよ。

【制約】
・1≤|S|,|T|≤1000
[例]
S="pirikapirirara"
T="poporinapeperuto"
答え: 6 ("ppriar" が長さ最大です)
[解法]
dp[i+1][j+1]:=Sのi文字目までとTのj文字目まででのLCSの長さとする。
今まではdp[i]を使ってdp[i+1]を表したりしましたが今回はdp[i][j],dp[i+1][j],dp[i][j+1]を使ってdp[i+1][j+1]を表すことを考えると次のようになる
・S[i] == T[j]ならば、dp[i][j]に対して、共通のSのi文字目とTのj文字目を付け加えれば1文字伸びるので
dp[i+1][j+1] = dp[i][j]+1
・dp[i+1][j]に対して、Tのj文字目を考慮しても特にLCSの長さは変わらず、
dp[i+1][j+1] = dp[i+1][j]
・dp[i][j+1]に対して、Sのi文字目を考慮しても特にLCSの長さは変わらず、
dp[i+1][j+1]=dp[i][j+1]
まとめると
dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1] (S[i] == T[j]

dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])(S[i]!=T[j]

<DP初期条件>
dp[0][0] = 0;
<求める値>
dp[|S|][|T|]

```
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int INF = 1 << 29;
string S, T;
int dp[1010][1010];
int main(){
	cin >> S >> T;
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < S.size(); ++i) {
		for (int j = 0; j < T.size(); ++j) {
			if (S[i+1] == T[j+1])
				dp[i + 1][j + 1] = dp[i][j] + 1;
			else
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
		}
	}
	cout << dp[S.size()][T.size()];
		return 0;
}
```
問題 9:　最小コスト弾性マッチング問題
系列 A=(a0,a1,…,am−1), B=(b0,b1,…,bn−1)が与えられる。各ペア(ai,bj)をマッチさせたときのコストは c(i,j)で与えられる。最小コスト弾性マッチングを求めよ。

【制約】
・1≤m,n≤1000
[解法]
dp[i+1][j+1]:=a[i]までとb[i]まででの弾性マッチングの最小コストとする。
dp[i][j],dp[i+1][j],dp[i][j+1]を使ってdp[i+1][j+1]を表すことを考えると次のようになる
・dp[i][j]に対して、新たにペア(a[i],b[j])をマッチさせて
　dp[i+1][j+1]=dp[i][j]+c(i,j)
・dp[i+1][j]に対して、新たにペア(a[i],b[j])をマッチさせて
  dp[i+1][j+1]=dp[i+1][j]+c(i,j)
・dp[i][j+1]に対して、新たにペア(a[i],b[j])をマッチさせて
　dp[i+1][j+1]=dp[i][j+1]+c(i,j)
まとめると
<DP漸化式>
dp[i+1][j+1]=min(dp[i][j],dp[i+1][j],dp[i][j])+c(i,j)
<初期条件>
dp[0][0]=0
<求める値>
dp[m][n]

問題 10:　レーベンシュタイン距離 (diffコマンド)
2つの文字列 S, Tが与えられます。Sに以下の3種類の操作のいずれかを順次実施して Tに変換したいです。そのような一連の操作のうち、操作回数の最小値を求めよ。

(操作)
＜変更＞ Sの中から文字S[ i ]を1個選んで、その文字を好きな文字に変更します。
＜削除＞ Sの中から文字S[ i ]を1個選んで、その文字を削除します。削除によって空文字列になることも許容します。
＜挿入＞ Sの好きな箇所に好きな文字を挿入します。特に、Sの先頭や最後尾に文字を追加することもできます。

【制約】
・1≤|S|,|T|≤10001≤|S|,|T|≤1000
[解法]
dp[i+1][j+1]:=Sのi文字目までを変換してTのj文字目までへと変換するための最小操作回数とする。
dp[i][j],dp[i+1][j],dp[i][j+1]を使ってdp[i+1][j+1]を表すことを考えると
・変換操作
　S[i]=T[j]なら、dp[i+1][j+1]=dp[i][j]
  S[i]!=T[j]なら、dp[i+1][j+1]=dp[i][j]+1
・削除操作(Sのi文字目を削除)
  dp[i+1][j+1]=dp[i][j+1]+1
・挿入操作(Tのj文字目の後ろに挿入)
  dp[i+1][j+1]dp[i+1][j]+1
<DP漸化式>
dp[i+1][j+1]=min(dp[i][j],dp[i][j+1]+1,dp[i+1][j])(S[i]==T[i]

dp[i+1][j+1]=min(dp[i][j]+1,dp[i][j+1]+1,dp[i+1][j]+1)
<DP初期条件>
dp[0][0]=0

```
#include<string>
#include<algorithm>
using namespace std;

const int INF = 1 << 29;
int n, m;
string S, T;
int dp[1010][1010];
int main(){
	cin >> n >> m >> S >> T;
	for (int i = 0; i < 1010; ++i)
		for (int j = 0; i < 1010; ++j)
			dp[i][j] = INF;
	dp[0][0] = 0;

	for (int i = -1; i < (int)S.size(); ++i) {
		for (int j = -1; j < (int)T.size(); j++){
			if (i == -1 && j == -1)continue;
			if (i >= 0 && j >= 0) {
				if (S[i] == T[j])dp[i + 1][j + 1] = dp[i][j];
				else dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);

			}
			if (i >= 0)dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j + 1] + 1);
			if (j >= 0)dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i + 1][j] + 1);

		}
	}

	cout << dp[S.size()][T.size()];
		return 0;
}

```