算法笔记-第十章-动态规划2

算法笔记-第十章-动态规划2 最大连续子序列和最大连续子序列和的最优方案最长上升子序列最长上升子序列的最优方案最长公共子序列(LCS)最长回文字符串题目一题目二

最大连续子序列和

对于最大连续数组求和的问题，设置一个dp数组，然后进行分开讨论边界的问题： 1.最大和就是A[i]本身 2.最大和是dp[i-1]+A[i]，即A[P]+…A[i-1]+A[i]=dp[i-1]+A[i]

由于这两种情况，于是得到了状态转移方程：dp[i]=max(A[i],dp[i-1]+A[i])

//最大连续子序列之和 #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 10000; const int INF = 0x3fffffff; int a[MAXN];//a[i]存放序列，dp[i]存放以A[i]结尾的连续序列的最大和 int dp[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } dp[0] = a[0]; //状态转移方程 for (int i = 1; i < n; i++) { dp[i] = max(a[i], dp[i - 1] + a[i]); } //dp[i]存放以a[i]结尾的连续序列的最大和，需要便利i得到最大的才是结果 int maxResult = -INF; for (int i = 0; i < n; i++) { maxResult = max(maxResult, dp[i]); } printf("%d", maxResult); return 0; } 最大连续子序列和的最优方案

//最大连续子序列和的最优方案 #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 10000; int a[MAXN]; int dp[MAXN], start[MAXN];//开始和结束的下标数组 int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } dp[0] = a[0]; start[0] = 0; for (int i = 1; i < n; i++) { if (dp[i - 1] >= 0) { dp[i] = dp[i - 1] + a[i]; start[i] = start[i - 1]; } else { dp[i] = a[i]; start[i] = i; } } int k = 0; for (int i = 1; i < n; i++) { if (dp[i] > dp[k]) { k = i; } } printf("%d %d %d", dp[k], start[k] + 1, k + 1); return 0; } 最长上升子序列

问题分析： 最原始的方法就是暴力解法，枚举每一种情况 ，即对于每个元素有取和不取两种选择，然后进行判断序列是否为不下降序列。

如果没有则更新最大长度，知道枚举完所有的情况并且得到最大长度。

1.方法就是：令dp[i]表示以A[i]结尾的最长不下降序列长度(和最大连续子序列和问题一样，以A[i]结尾是强制性的要求，对于A[i]就有着两种可能性

2.如果存在A[i]之前的元素A[j],(j<i)，使得A[j]<=A[i]且dp[j]+1>dp[i],(即把A[i]跟在以A[j]结尾的LIS后面能比当前以A[i]结尾的LIS长度更长), 那么就把A[i]，跟在以A[j]，结尾的LIS后面，形成一条更长的不下降序列。(dp[i]=dp[j]+1)

3.如果A[i]之前的元素都比A[j]大，那么A[i]就只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个A[i]。

那么A[i]结尾的LIS长度就是两个情况的最大长度。

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 100; int a[MAXN]; int dp[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int maxLen = 0;//记录最大的dp[i] for (int i = 0; i < n; i++) {//按照顺序计算出dp[i]的值 dp[i] = 1;//边界初始化条件，(即先假设每一个元素自成一个子序列） for (int j = 0; j < i; j++) { if (a[j] <= a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1;//状态转移方程，用以更新dp[i] } } maxLen = max(maxLen, dp[i]); } printf("%d", maxLen); return 0; } 最长上升子序列的最优方案

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100; int a[MAXN]; int dp[MAXN], pre[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } memset(pre, -1, sizeof(pre)); int k, maxLen = 0; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (a[j] <= a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } if (dp[i] > maxLen) { maxLen = dp[i]; k = i; } maxLen = max(maxLen, dp[i]); } vector<int> maxLenSeq; while (k != -1) { maxLenSeq.push_back(a[k]); k = pre[k]; } reverse(maxLenSeq.begin(), maxLenSeq.end()); printf("%d\n", maxLen); for (int i = 0; i < maxLenSeq.size(); i++) { printf("%d", maxLenSeq[i]); if (i < (int)maxLenSeq.size() - 1) { printf(" "); } } return 0; } 最长公共子序列(LCS)

对待这样的题目动态规划的思路是：令dp[i][j]来表示字符串A的i位和字符串B的j号位之前的LCS长度。

若A[i]==B[j],则字符串A与字符串B的LCS增加1位，即有dp[i][j]=dp[i-1][j-1]+1

若A[i]!=B[j]，则A的i号位和B的j号位之前的LCS无法延长。因此 dp[i][j] 就会继承dp[i-1][j]与dp[i][j-1]中的较大值，即有dp[i[j]=max{dp[i-1][j],dp[i][j-1]}

#include <iostream> #include <string> #include <algorithm> using namespace std; const int MAXN = 100 + 1; int dp[MAXN][MAXN]; int main() { string s1, s2; cin >> s1 >> s2; for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } printf("%d", dp[s1.length()][s2.length()]); return 0; } 更为详细的解释补充：边界问题，dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m) //补充：边界问题，dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m) #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100; const A[N], B[N]; int dp[N][N]; int main() { int n; gets(A + 1);//从下标1开始读入 gets(B + 1); int lenA = strlen(A + 1);//由于读入的时候是从1开始读入的，因此读取长度也是从+1开始的 int lenB = strlen(B + 1); //边界 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 = 0; i <= lenA; i++) { for (int j = 0; j <= lenB; j++) { if (A[i] == B[j]) 如果（A[i]==B[日]） { dp[i][j] = dp[i - 1][j - 1] + 1; DP[I][J]=DP[I-1][J-1]+1; } else 还 { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); dp[i][j]=max（dp[i-1][j]，dp[i][j-1]）; } } } printf("%d", dp[lenA][lenB]); printf（“%d”，dp[lenA][lenB]）; } 最长回文字符串

解题思路：令dp[i][j]表示s[i]至s[j]所表示的子串是否是回文字符串 是则是1，不是则是0，这样根据s[i]是否等于s[j],可以将情况为两类 令dp[i][j]表示s[i]至s[j]所表示的子串是否是回文字符串 是则是1，不是则是0，这样根据s[i]是否等于s[j], 可以将情况为两类 1，若s[i] == s[j], 那么只要s[i + 1]至s[j - 1]是回文子串，s[i]至s[j]就是回文子串 如果不是，那也不是回文子串 2，若s[i] != s[j], 那么s[i]至s[j]一定不是回文子串

由此可以写出状态转移方程： **dp[i][j] = { dp[i + 1][j - 1],s[i] = s[j]; 0,s[i]!=s[j] }** 边界：边界： dp[i][i]=1,dp[i][i+1]=(s[i]==s[i+1])?1:0问题=如果按照i和j从小到大的顺序来枚举子串的两个端点 然后更新d[i][j]无法确定d[i+1][j-1]就已经被计算过 所以最好的选择就是用： 根据递推的写法从边界出发原理，按子串的长度和子串的初始位置就行枚举

左边端点为i，右边端点为i+L-1//L表示子串的长度，也可以是整个字符串的长度

题目一

#include <iostream> #include <string> #include <algorithm> using namespace std; const int MAXN = 100 + 1; int dp[MAXN][MAXN]; int main() { string s1, s2; cin >> s1 >> s2; for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } printf("%d", dp[s1.length()][s2.length()]); return 0; } 题目二

给出一个字符串S，求出S的最长回文字符串的长度 样例： 字符串"PATZJUJZTACCBC"的最长回文字符串为"ATZJUJZTA"长度为9

#include<cstdio> #include<string> const int N = 1010; char s[N]; int dp[N][N]; int main() { gets(s); int len = strlen(s), ans = 1; memset(dp, 9, sizeof(dp));//dp数组的初始化为0 //边界 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; 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;//更新最长回文字符串的长度 } } } printf("%d\n", ans); return 0; }