線性dp

數字三角形

P1216 數字三角形 - 洛谷

題目

觀察下面的數字金字塔。

寫一個程序來查找從最高點到底部任意處結束的路徑，使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

思路

每個數字只能有上方，左上，數字遞推而來。最后計算最底層最大值。

int a[1100][1100],f[1100][1100];
void solve()
{int n;cin>>n;fir(i,1,n)fir(j,1,i){cin>>a[i][j];}fir(i,1,n){fir(j,1,i)f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];}int mx=0;fir(i,1,n)mx=max(f[n][i],mx);cout<<mx<<'\n';
}

• 那如果向左和向右移動次數相差不能大于1，最大值又是多少了？

  易知，當n為偶數，最后一層落在的點一定在n/2或n/2+1.而n為奇數時，最后一層落在的點一定在n/2+1

LIS（最長上升子序列）

例題

B3637 最長上升子序列 - 洛谷 | 計算機科學教育新生態

數組f【i】，用來存儲以a【i】作末尾的上升子序列長度。

代碼（n^2）

#include<bits/stdc++.h>
using namespace std;
int a[1000050],f[100050];
int main()
{int n,ans=1;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]; fill(f,f+n+2,1);//初始化for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[j]<a[i])//遞增f[i]=max(f[i],f[j]+1);}ans=max(ans,f[i]);}cout<<ans<<'\n';
}

二分優化（nlogn）

維和一個數組b,存放上升子序列。 其中 b[i]表示長度為 i 的上升子序列的最小末尾元素。

從前往后遍歷數組a

• a[i]>b[len]末尾元素,b[++len]=a[i]
• a[i]<=b[len],用a[i] 替換b數組第一個>=a[i]的元素

最終b數組的長度便是答案

用vector和lower_bound實現

#include<bits/stdc++.h>
using namespace std;
int n,a[1000050];
int main()
{cin>>n;vector<int> d;for(int i=0;i<n;i++){    cin>>a[i];auto it=lower_bound(d.begin(),d.end(),a[i]);if(it==d.end())d.push_back(a[i]);else *it=a[i];}cout<<d.size();
}

LCS(最長公共子序列)

這個視頻講的不錯E05 線性DP 最長公共子序列，本文思路節選于此視頻

例題

U165581 最長公共子序列（Longest Common Subsequence，LCS） - 洛谷 | 計算機科學教育新生態

設 f[i][j] 表示序列 a[1...i] 和 b[1...j] 的最長公共子序列長度。

現在判斷末尾元素 a[i] 與 b[j] 是否在公共子序列中：

1. 若 a[i] = b[j]：
   • 則 a[i] 與 b[j] 在公共子序列中。
   • 遞推關系：f[i][j] = f[i-1][j-1] + 1
2. 若 a[i] ≠ b[j]，且 a[i] 不在公共子序列中：
   • 則可去掉 a[i]。
   • 遞推關系：f[i][j] = f[i-1][j]
3. 若 a[i] ≠ b[j]，且 b[j] 不在公共子序列中：
   • 則可去掉 b[j]。
   • 遞推關系：f[i][j] = f[i][j-1]

狀態轉移方程：

$$f[i][j]=\{\begin{array}{ll}f[i?1][j?1]+1,& \text{若?}a[i]=b[j]\\ \max (f[i?1][j],f[i][j?1]),& \text{若?}a[i]\ne b[j]\end{array}$$
邊界條件：

$f[0][j]=0;f[i][0]=0;$

代碼

int n,f[N][N];
int main()
{   string a,b;cin>>a>>b;for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){if(a[i]==b[j])f[i+1][j+1]=f[i][j]+1;elsef[i+1][j+1]=max(f[i][j+1],f[i+1][j]);}cout<<f[a.size()][b.size()];
}

LCS——>>LIS

例題

P1439 【模板】最長公共子序列 - 洛谷

思路

此題特殊之處在于：全排列

數據范圍大，N^2不行

既然兩個數組都是1-n的全排列，那么可以用一個新的數組c存放b[i]在數組a中的位置，只有c中遞增的子序列才可構成a,b的公共子序列。這樣題目就轉化為求最長上升子序列了

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],c[N];
int main()
{   cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]=i;//哈希}for(int i=1;i<=n;i++){ int x;cin>>x;c[i]=b[x];//LCS——>LIS}vector<int> v;//二分優化的最長上升子序列for(int i=1;i<=n;i++){auto it=lower_bound(v.begin(),v.end(),c[i]);if(it==v.end()) v.push_back(c[i]);else *it=c[i];}cout<<v.size(); 
}

最長公共子串

• 公共子串：字符必須是連續相等的

• 公共子序列：字符必須是相等的，可以不連續

  設 f[i][j] 表示序列 a[1...i] 和 b[1...j] 的最長公共子串長度。

與最長公共子序列類似，遞推公式有所不同。
$$f[i][j]=\{\begin{array}{ll}f[i?1][j?1]+1,& \text{若?}a[i]=b[j]\\ 0，& \text{若?}a[i]\ne b[j]\end{array}$$
最長公共子串不一定是以n,m結尾的，需要比較出最大值。

最長公共上升子序列（LCIS）

這是LIS和LCS的結合。

動態規劃狀態轉移

1. 初始化：我們初始化一個二維數組 f，大小為 (n+1) x (n+1)，并將所有元素初始化為 0。這里 n 是序列 A 和 B 的長度。

2. 狀態轉移：

   首先判斷公共子序列中是否包含a[i]

   • 不包含a [i]的子集，最大值是f[i-1] [j]

   • 包含a[i] 的子集，將這個子集繼續劃分,依據是子序列的倒數第二個元素在b[]中是哪個數（也就是由誰遞推而來）

     所以需要一個mx，來記錄在當前 i 的條件下，滿足 a[i] > b[k] 的 f[i - 1][k] + 1 的前綴最大值。

3. 優化：為了提高效率，我們可以在遍歷 j 的過程中維護一個最大值 mx，表示在當前 i 的情況下，所有 f [i-1] [k] 的最大值，其中 k < j 且 B[k] < A[i]。這樣，我們就可以在 O(1) 的時間更新 f[i][j]。

• f[i][j] 表示所有 a[1 ~ i] 和 b[1 ~ j] 中以 b[j] 結尾的公共上升子序列的長度最大值。
• mx 用于記錄在當前 i 的條件下，滿足 a[i] > b[k] 的 f[i - 1][k] + 1 的前綴最大值。
• 下面代碼是一維優化后的代碼

int a[3050],b[3050],f[3050];
void solve()
{int n,mx;cin>>n;fir(i,1,n)cin>>a[i];fir(i,1,n)cin>>b[i];fir(i,1,n)//只看前i個{mx=1;fir(j,1,n){if(a[i]==b[j]) f[j]=max(f[j],mx);if(a[i]>b[j]) mx=max(mx,f[j]+1);}}mx=0;fir(i,1,n)mx=max(f[i],mx);cout<<mx<<'\n';
}