dp動態規劃2
===
---
DP可以被分類成xDyD的形式
x代表有$O(n^x)$個狀態
y代表轉移式需要$O(n^y)$
像費氏數列就是1D0D的DP
---
### Longest Common Subsequence(LCS)
----
LCS是序列分析重要的問題
目標是找出最長共同子序列
像TeacherLikeEgg這個字串中
Tea、cher、TLE都是子序列
而ggE不是，因為不能調整序列順序
LCS可以拿來作為字串相似度的定義
有很多應用
----
[例題](https://judge.tcirc.tw/ShowProblem?problemid=d070)
給兩個字串，求兩字串的LCS
----
首先最簡單的方法還是暴力
但一個字串有$2^n$個子序列
很明顯時間不允許
----
假設兩個字串分別是s1,s2
定義$dp[i][j]$為s1的前$i$個字元與
s2的前$j$個字元LCS的長度
當搜尋到$i$,$j$時有兩種狀況，
$s1[i]$==$s2[j]$ 或 $s1[i]$!=$s2[j]$
把兩個分開來討論
----
當 $s1[i]$==$s2[j]$
代表這個字元可以加進LCS
所以 $dp[i][j]=dp[i-1][j-1]+1$
----
而 $s1[i]$!=$s2[j]$時
代表兩邊至少有一邊對LCS沒有幫助
而因為要取最大的
所以轉移式可以寫成
$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
----
確定好轉移式後
還要設定初始條件
$dp[i][0]$代表其中一邊長度是0的字串和
某字串的LCS長度
既然一邊是空字串，那LCS一定也是空字串
所以$dp[i][0]=dp[0][j]=0$
----
整理起來就是
\begin{aligned}
dp[i][j]=
\begin{cases}
0\quad if\quad i=0\ or\ j=0 \\
dp[i-1][j-1]+1\quad if\ s1[i]=s2[j] \\
max(dp[i-1][j],dp[i][j-1]) \ else
\end{cases}
\end{aligned}
----
code
```cpp=
//直接拿這個丟到judge不會過可以自己想想原因
#include<bits/stdc++.h>
using namespace std;
signed main(){
string s1,s2;
cin>>s1>>s2;
int n=s1.size(),m=s2.size();
int dp[105][105];
memset(dp,0,sizeof(dp));//把dp中所有元素設定成0
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[n][m];
return 0;
}
```
----
這裡用到一個叫memset的東東
他可以用來初始化內存
通常被用來初始化0或極大、小值
之後圖論蠻容易用到的
用法:
```cpp=
memset(變數名,0,sizeof(變數名))//全設成0
memset(變數名,0x7f,sizeof(變數名))//全設成極大值
memset(變數名,0x8f,sizeof(變數名))//全設成極小值
```
---
1D1D問題
----
上次的apcs[第四題](https://zerojudge.tw/ShowProblem?problemid=m373)就是一個1D1D的問題
這裡來講解要如何寫這題
----
題敘
```
你擁有一個長度為n的陣列，代表每天的投資收益，以及k張金牌。
你可以自行決定投資的開始和結束日期。在你選擇投資的每一天
，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。
你的目標是找出如何投資，以實現最大的總收益。
請注意，你只能在投資期間進出一次。
```
----
這題當k=0時其實就是 __最大連續子陣列__ 的問題
但他多了免死金牌
所以狀態必須加上"用了幾個金牌"
----
設$dp[i][j]$為
結束在第$i$天，用掉$j$個金牌所獲得利潤的最大值
邊界條件：第0天的利潤是0
所以$dp[0][j]$=0
----
轉移式：
首先我們先不管金牌只討論$dp[i][0]$
這跟最大子陣列一樣
$dp[i][0]=max(dp[i-1][0]+a[i],a[i])$
----
接下來當k>0時
轉移式會是
$dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+a[i] :j<=k)$
----
整理起來就是這樣
\begin{aligned}
dp[i][j]=
\begin{cases}
0\quad if\quad i=0 \\
max(dp[i-1][j-1],dp[i-1][j]+a[i] :0<j<=k)
\end{cases}
\end{aligned}
----
code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5e5+5;
int k,n,a[N],dp[N][25];
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
ans=max(ans,dp[i][0]);
for(int j=1;j<=k;j++){
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+a[i]);
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
}
```
---
### LIS
----
LIS是經典的1D1D問題
要找出最大的遞增或遞減子序列
----
[題目](https://judge.tcirc.tw/ShowProblem?problemid=d078)
這題就是要找最大遞增子序列
----
假設序列是$a[1:n]$
定義$dp[i]$為到$i$為止的LIS
轉移式就是
$dp[i]=max(dp[j]+1 :j<i \ and \ a[j]<a[i])$
這樣直接做複雜度會是$O(n^2)$
但還有更快的方法
----
設$last[i]$為 __LIS長度為$i$的最小可能結尾__
$L$為目前LIS的長度
那就可以進行以下操作
```cpp=
last[0]=a[1];
L=1;
for(int i=2;i<=n;i++){
for(int j=0;j<L;j++){
if(last[j]>= a[i]){
last[j]=a[i];
if(j==L) L++;
break;
}
}
}
```
----
但這樣在找$last[j]>=a[i]$複雜度還是$O(n)$
整體還是$O(n^2)$
不過其實last是一個遞增序列
所以可以用二分搜來找
這樣整體複雜度就是$O(nlogn)$
----
code
```cpp=
int n,last[100005],L;
cin>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
int it=lower_bound(last,last+len,a)-last;
last[it]=a;
if(it==len) len++;
}
cout<<len;
```
----
code2
```cpp=
int n,a;
vector<int> v;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
auto it=lower_bound(v.begin(),v.end(),a);
if(it==v.end()) v.push_back(a);
else *it=a;
}
cout<<v.size();
```
---
### 小技巧
----
拿個題目舉例
```
給一個二維陣列，長寬為n和m，由大於等於0的數字組成，代表有幾個蘋果，
之後給個座標，問上下左右共有幾個蘋果
輸入例:
3 3
1 2 2
1 2 3
0 0 0
1 2
輸出例:
5
```
----
這時有人會寫四個式子像以下程式
----
```cpp=
int n,m,a[105][105],x,y;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>x>>y;
int ans=0;
ans+=a[x+1][y];
ans+=a[x-1][y];
ans+=a[x][y-1];
ans+=a[x][y+1];
cout<<ans;
```
----
這裡光是加四個方向就寫了四行
如果要附近八個方向或做更複雜的計算
程式碼就會變很長
所以就可以用以下方法
----
```cpp=
int n,m,a[105][105],x,y;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>x>>y;
int ans=0,nx[4]={0,0,1,-1},ny[4]={1,-1,0,0};
for(int i=0;i<4;i++)
ans+=a[x+nx[i]][y+ny[i]];
cout<<ans;
```
----
大家可以用這方法去寫APCS的
[這題](https://zerojudge.tw/ShowProblem?problemid=m932)只是需要一點變化
---
### 結束 Ya
{"title":"dp動態規劃2","description":"","contributors":"[{\"id\":\"443d51bf-5a61-411d-b3cb-c3371649227c\",\"add\":4871,\"del\":278}]"}