PAT A1007 动态规划

这道题也是动态规划的几大问题之一，也就是最大连续序列和问题；对于这个问题，我们需要考虑的首先还是转换方程的问题：我们设置一个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;}