线性dp
1.最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
|
dp[i] |
1 |
1 |
1 |
1 |
2 |
3 |
4 |
1 |
#include<iostream>
#include<algorithm>
#define n 8
using namespace std;
int main(){
int a[n];
int dp[n];
fill(dp,dp+n,1);
for(int i=0;i<n;i++){
cin>>a[i];
}
int maxn=1;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(a[j]>a[i])
dp[j]=max(dp[j],dp[i]+1);
if(dp[j]>maxn) maxn=dp[j];
}
}
cout<<maxn;
return 0;
}
2.最长公共子序列
定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
|
i j |
0 |
1 a |
2 c |
3 e |
|
0 |
0 |
0 |
0 |
0 |
|
1 a |
0 |
1 |
1 |
1 |
|
2 b |
0 |
1 |
1 |
1 |
|
3 c |
0 |
1 |
2 |
2 |
|
4 d |
0 |
1 |
2 |
2 |
|
5 e |
0 |
1 |
2 |
3 |
#include<iostream>
#include<vector>
using namespace std;
int main(){
string text1,text2;
cin>>text1>>text2;
int m = text1.size();
int n = text2.size();
if(!m||!n)
return 0;
vector<vector<int> > dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(text1[i-1]==text2[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[m][n];
}
2.0滚动数组
#include<iostream>
#include<vector>
using namespace std;
int main(){
string text1,text2;
cin>>text1>>text2;
int m = text1.size();
int n = text2.size();
if(!m||!n)
return 0;
vector<vector<int> > dp2(2,vector<int>(n+1,0));//dp[2][n+1]滚动数组
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(text1[i-1]==text2[j-1])
dp2[i&1][j]=dp2[(i-1)&1][j-1]+1;
else
dp2[i&1][j]=max(dp2[(i-1)&1][j],dp2[i&1][j-1]);
}
}
cout<<dp2[m&1][n];
}
3.三角形最短路径和
|
i j |
0 |
1 |
2 |
3 |
4 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
INF |
2 |
INF |
INF |
INF |
|
2 |
INF |
5 |
6 |
INF |
INF |
|
3 |
INF |
11 |
10 |
13 |
INF |
|
4 |
INF |
15 |
11 |
18 |
16 |
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为11（即，2+3+5+1= 11）。
#include<iostream>
#include<vector>
#include<limits>
#define n 4
using namespace std;
int main(){
int a[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
int ans=INT_MAX;
vector<vector<int> > dp(n+1,vector<int>(n+1,INT_MAX));
for(int i=0;i<5;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+a[i][j];
}
}
for(int i=1;i<=n;i++){
ans=min(ans,dp[n][i]);
}
cout<<ans;
return 0;
}
4.最大子序和
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释:连续子数组[4,-1,2,1] 的和最大，为6。
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
dp[i] |
0 |
-2 |
1 |
-2 |
4 |
3 |
5 |
6 |
1 |
5 |
#include<iostream>
#include<algorithm>
#include<climits>
#define n 9
using namespace std;
int main(){
int a[n+1];
int dp[n+1];
fill(dp,dp+n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=INT_MIN;
for(int i=1;i<=n;i++){
dp[i]=max(dp[i-1]+a[i],a[i]);
if(dp[i]>ans) ans=dp[i];
}
cout<<ans;
return 0;
}