动态规划-序列问题

注意这个题目要“连续”

//dp[i]以A[i]作为末尾的连续序列最大和 #include <cstdio> #include<algorithm> #include<iostream> using namespace std; const int maxn = 10010; int A[maxn], dp[maxn]; int main(){ int n; cin >> n; for (int i = 0; i < n; i++) { cin >> A[i]; } //边界 dp[0] = A[0]; //状态转移方程 for (int i = 1; i < n; i++) { dp[i] = max(A[i], dp[i - 1] + A[i]); } int k = 0; for (int i = 0; i < n; i++) { if (dp[i] > dp[k]) { k = i; } } cout << dp[k]; return 0; }

不下降字符子序列（不用连续）：

//最长不下降子序列 #include <cstdio> #include<algorithm> #include<iostream> using namespace std; const int maxn = 10010; int A[maxn], dp[maxn]; int main(){ int n; cin >> n; for (int i = 0; i <= n; i++) { cin >> A[i]; } int ans = -1; for (int i = 0; i <= n; i++) { dp[i] = 1;//边界初始 每个元素自成一个序列 for (int j = 1; j < i; j++) { if (A[i] >= A[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; } } ans = max(ans, dp[i]); } cout << ans; return 0; }

最长公共子序列：

#include "pch.h" //最长公共子序列 //dp[i][j]:A串i号位和B串J号位之前的LCS长度 #include <cstdio> #include<algorithm> #include<string> #include<iostream> using namespace std; const int maxn = 10010; int dp[maxn][maxn]; string A, B; int main(){ int n; cin >> A; cin >> B; int lenA = A.length(); int lenB = B.length(); for (int i = 0; i <= lenA; i++) { dp[i][0] = 0; } for (int j = 0; j < lenB; j++) { dp[0][j] = 0; } //状态转移 for (int i = 1; i <= lenA; i++) { for (int j = 1; j <= lenB; j++) { if (A[i] == B[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } cout << dp[lenA][lenB]; return 0; }

最长回文子串

注意一个问题，这里如果固定i枚举j或者固定j枚举i总是会有得不到的子问题，所以按照长度递增的顺序来枚举：

#include "pch.h" //最长回文子串 //dp[i][j]:A串i号位和B串J号位之前的LCS长度 #include <cstdio> #include<algorithm> #include<string> #include<iostream> using namespace std; const int maxn = 10010; int dp[maxn][maxn]; string S; int main(){ int ans = 1; cin >> S; int len = S.length(); memset(dp, 0, sizeof(dp)); for (int i = 0; i < len; i++) { dp[i][i] = 1; if (i < len - 1) { if (S[i] == S[i + 1]) { dp[i][i + 1] = 1;//是回文串设1 非设0 ans = 2;//当前最长数 } } } for (int L = 3; L <= len; L++) { for (int i = 0; i + L - 1 < len; i++) { int j = i + L - 1;//子串右端点 if (S[i] == S[j] && dp[i + 1][j - 1] == 1) { dp[i][j] = 1; ans = L; } } } cout << ans; return 0; }