网站建设师薪资/软文营销网站

最大连续子序列和

对于最大连续数组求和的问题，设置一个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;
}