# DP

一個由小問題推到大問題的演算算

## 費氏數列

### 純遞迴版

int fib(int N) {
	if( N == 1 || N == 0 ) return 1;
	return fib(N-1)+fib(N-2);
}

digraph {
	a[label="4"]
	b[label="3"]
	c[label="2"]
	d[label="1"]
	e[label="0"]
	a -> b[color=red]
	b -> c[color=red]
	c -> d[color=red]
	c -> e[color=red]
	
	d -> c[label="1", color=green]
	e -> c[label="1", color=green]
	c -> b[label="2", color=green]
	
	f[label="1"]
	b->f[color=red]
	f->b[label="1", color=green]
	
	b->a[label="3", color=green]
	
	
	g[label="2"]
	a->g[color=red]
	
	h[label="1"]
	g->h[color=red]
	h->g[label="1", color=green]
	
	i[label="0"]
	g->i[color=red]
	i->g[label="1", color=green]
	
	
	g->a[label="2", color=green]
}

$$時空複雜度O(\phi^N)$$

### 動態規劃版

int save[mxN]; //mxN==100000
save[0] = save[1] = 1;
int fib(int N) {
	if( save[N] ) return save[N]; //if( save[N] != 0 )
	else {
		save[N] = fib(N-1)+fib(N-2);
		return save[N];
	}
}

digraph {
	"4" -> "3"
	"3" -> "2"
	"2" -> "1"
	"1" -> "2"[label=1, color=green]
	"2" -> "0"
	"0" -> "2"[label=1, color=green]
	"2" -> "3"[label=2, color=green]
	"3" -> "4"[label=3, color=green]
	"4"->"2"
	"2"->"4"[label=2, color=green]
}

$$時空複雜度O(N)$$

### 迭代版

int dp[mxN]; //mxN=100
dp[0] = dp[1] = 1;
for( int i = 2; i < mxN; ++i ){
	dp[i] = dp[i-1] + dp[i-2];
}

$$時空複雜度O(N)$$

<font color = white>

$$$$

</font>

### 最常共同子序列

$a \, =\,accd$
$b \, =\,adcc$
$dp[i][j] \implies a字串取到第i個,b自串取到第j個時的LCS$
{
$$
dp[i][j] = \begin{cases}
dp[i-1][j-1]+1\quad &if \quad a_i = b_j \\
max( dp[i][j-1], dp[i-1][j]) \quad &else
\end{cases}
$$
}

把下方code中註釋掉的那兩行拔掉即可

### 最常連續共同子序列

$a \, =\,accd$
$b \, =\,adcc$
$dp[i][j] \implies a字串取到第i個,b自串取到第j個時的LCS$
{
$$dp[i][j] = \begin{cases}
dp[i-1][j-1]+1\quad &if \quad a_i = b_j \\
\end{cases}$$
}

constexpr int mxN = 100002;
int dp[2][mxN];
void solve(string &s1, string &s2) {
	memset( dp, 0, sizeof(dp));
	s1 = "+"+s1; // + has no mean
	s2 = "+"+s2;
	const int s1_len = s1.size(), s2_len = s2.size();
	int mx = 0;
	for( int i = 1; i < s1_len; ++i) {
		for( int j = 1; j < s2_len; ++j ){
			if( s1[i] == s2[j] )
				dp[i&1][j] = dp[~i&1][j-1]+1;	 //i&1 i%2, ~i&1 (i+1)%2
			else 
				dp[i&1][j] = 0;
			mx = max( dp[i&1][j], mx);
			//else  [with no continue]
			//	dp[i&1][j] = max( dp[i&1][j-1], dp[~i&1][j] );
		}
		//for( int _ = 1; _ < s2_len; _++ ) cout << dp[i&1][_] << ' ';
		//cout << endl;
	}
	cout << mx << '\n';
}