关于线性DP模板

关于线性DP模板

线性DP是动态规划中最简单的一种，刚入门从这些模板中学习一下。

---

数字三角形

来源：数字三角形 - OpenJ_Bailian 2760 - Virtual Judge

思路

• DP递推一定是从最开始推到最终的状态
• 路径的尽头一定是三角形最上方，我们从最下面开始递推
• 每次取较大的那个相加，使得本步骤最优：$f[i][j]=max(f[i+1][j],f[i+1][j+1])$

代码

void solve()
{cin >> n;for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)cin >> a[i][j];for(int i=n-1; i>=1; i--){for(int j=1; j<=i; j++)a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}cout << a[1][1];
}

---

最长上升子序列

来源：B3637 最长上升子序列 - 洛谷

思路

• 当遇到比当前序列都大的元素时将其添加到末尾
• 如果不是就替换第一个大于等于它的元素，这样不会改变原有的长度并使整个序列尽量小，加入更多元素

代码

void solve()
{cin >> n;for(int i=1; i<=n; i++) cin >> a[i];int len=0;for(int i=1; i<=n; i++){int pos=lower_bound(b+1,b+len+1,a[i])-b;if(pos>len) b[++len]=a[i];else b[pos]=a[i];}cout << len;
}

---

最长公共子序列1（求长度）

来源：最长公共子序列（Longest Common Subsequence，LCS） - 洛谷 U165581 - Virtual Judge

思路

• 如果此时不匹配的话那就不能选，继承上一轮的状态或者左边的状态： $f[i][j]=max(f[i-1][j],f[i][j-1])$
• 如果此时匹配那么就是上一轮没选它时的状态再选上它：$f[i][j]=f[i-1][j-1]+1$

过程演示：

i\j	B	D	C	A	B
A	“”	“”	“”	“A”	“A”
B	“B”	“B”	“B”	“B”	“AB”
C	“B”	“B”	“BC”	“BC”	“BC”
B	“B”	“B”	“BC”	“BC”	“BCB”
D	“B”	“BD”	“BD”	“BD”	“BDB”
A	“B”	“BD”	“BD”	“BDA”	“BDB”
B	“B”	“BD”	“BD”	“BDA”	“BDAB”

代码

int f[N][N];
void solve()
{cin >> a >> b;a=' '+a,b=' '+b;for(int i=1; i<a.size(); i++)for(int j=1; j<b.size(); j++)if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;elsef[i][j]=max(f[i][j-1],f[i-1][j]);size_t s1=a.size();size_t s2=b.size();cout << f[s1-1][s2-1];return;
}

一维优化

• 由于二维数组非常的浪费，效率极其有限，所以我们可以像背包问题那样将其压缩成一维

• 由刚刚的分析可知：此时的状态只和当前轮和前一轮的状态有关，所以我们用一个p数组表示前一轮的状态就行

• $p[j]=f[i-1][j]$

int f[N],p[N];
void solve()
{cin >> a >> b;a=' '+a,b=' '+b;for(int i=1; i<a.size(); i++){for(int j=1; j<b.size(); j++){if(a[i]==b[j])f[j]=p[j-1]+1;elsef[j]=max(f[j-1],p[j]);}for(int j=0; j<=b.size(); j++) p[j]=f[j];//复制当轮状态}size_t s2=b.size();cout << f[s2-1];
}

---

最长公共子序列2（求子串）

来源：最长公共子序列Lcs - 51Nod 1006 - Virtual Judge

类似的，这个只是让求了长度，如果要求具体的子串呢？其实是一样的，可以再练练手

void solve()
{string a,b;cin >> a >> b;n=a.size(),m=b.size();a=' '+a,b=' '+b;for(int j=0;j<=m;j++) p[j]=f[j]="";for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(a[i]!=b[j]){if(f[j-1].size()>p[j].size())f[j]=f[j-1];else f[j]=p[j];}else f[j] = p[j-1] + a[i];}for(int j=0;j<=m;j++) p[j]=f[j];}cout << f[m];
}

---

最长公共子序列3（数字）

来源：P1439 【模板】最长公共子序列 - 洛谷

思路

• 重要的不是重复，而是相对位置
• 将第一个数组的元素下标映射到第二个数组，这样就得到了它们在下面的相对位置
• 由于最长公共子序列只能是从左往右不能回来，所以用LIS对下标进行处理

代码

void solve()
{cin >> n;map<int,int> mp;for(int i=1; i<=n; i++){cin >> x;mp[x]=i;}for(int i=1; i<=n; i++){cin >> x;a[i]=mp[x];}int len=0;for(int i=1; i<=n; i++){int pos=lower_bound(b+1,b+len+1,a[i])-b;if(pos>len) b[++len]=a[i];else b[pos]=a[i];}cout << len;
}

---

编辑距离

来源：P2758 编辑距离 - 洛谷

思路

• $f[i][j]$含义：将a前i个字符改为b前j个字符所需要的次数
• 初始化：将b无字符时转换成a前i字符需i次，下面同理
• 由于f数组将a与b的状态融为一体，不用考虑删减只用考虑增加
• 如果$a[i]==b[j]$则不用修改
• 若要修改就要探讨是否要增加、替换谁所用更少

代码

int f[N][N];//将a前i个字符改为b前j个字符所需要的次数
void solve()
{string a,b;cin >> a >> b;n=a.size(),m=b.size();a=' '+a,b=' '+b;for(int i=0; i<=n; i++) f[i][0]=i;//将b无字符转换成a前i字符需i次for(int j=0; j<=m; j++) f[0][j]=j;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){int k=1;if(a[i]==b[j]) k=0;//以谁为基准替换        还是增加f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+k);}}cout << f[n][m];
}