PAT A1007 动态规划

共计 642 个字符，预计需要花费 2 分钟才能阅读完成。

这道题也是动态规划的几大问题之一，也就是最大连续序列和问题；
对于这个问题，我们需要考虑的首先还是转换方程的问题：我们设置一个 dp 数组，dp[i] 代表的是到当前的最大序列和。
所以有转换方程：dp[i]=max(a[i],dp[i-1]+a[i]) 所以边界就是 dp[0]=a[0]，然后从 1 开始计算；
代码如下：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1010;
string data;
int matrix[maxn][maxn];
int main(){
getline(cin,data);
int len=data.size();
for(int i=0;i<len;i++){
matrix[i][i]=1;
}
int ans=1;
for(int i=1;i<len;i++){
if(data[i-1]==data[i]){
matrix[i-1][i]=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(data[i]==data[j]&&matrix[i+1][j-1]==1){
matrix[i][j]=1;
ans=L;
}
}
}
printf(“%d\n”,ans);
system(“pause”);
return 0;
}