先补充一下背包问题：
于是，我们把每一组当成一个物品，f[k][v]表示前k组花费v的最大值。
转移方程还是max(f[k-1][v],f[k-1][v-c[i]]+w[i])
伪代码（注意循环顺序）：
for 所有组：
for v=max.....0
for i：f[v]=max(f[v],f[v-c[i]]+w[i])
下面看看区间dp的应用：
下面是分析：
我们令f[i][j]表示从ai到aj的串中，有多少个匹配的括号。
我们分析最左边的，1.它匹配：f[i][j]=max(f[i][k]+f[k+1][j]),对于最后一个，若可以匹配+2，不可以就不加。
2.他不匹配：f[i][j]=max(f[i+1][j]);
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
string s;
int f(int i,int j){
if(i>=j) return dp[i][j]=0;
if(dp[i][j]!=-1) return dp[i][j];
for(int k=i+1;k<=j-1;k++){
if((s[i]=='('&&s[k]==')')||(s[i]=='['&&s[k]==']')) dp[i][j]=max(dp[i][j],f(i+1,k-1)+f(k+1,j)+2);
else dp[i][j]=max(dp[i][j],f(i+1,k-1)+f(k+1,j));
}
dp[i][j]=max(dp[i][j],f(i+1,j));
if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){
dp[i][j]=max(dp[i][j],f(i+1,j-1)+2);
}
else dp[i][j]=max(dp[i][j],f(i+1,j-1));
return dp[i][j];
}
int main(){
while(cin>>s){
if(s=="end") break;
memset(dp,-1,sizeof(dp));
cout<<f(0,s.size()-1)<<endl;
}
}接题：
法1，我们倒序求一串，相当于求他们的公共子序列。
法2.区间dp，f[i][j]表示ai,aj的最长回文子序列。
ai==aj f[i][j]=f[i+1][j-1]+2;
否则，f[i][j]=max(f[i+1][j],f[i][j-1])
下面是AC代码：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int a[1050][1050];
int n=s.length();
for(int j=0;j<=n-1;j++){
a[j][j]=1;
}
for(int j=1;j<=n-1;j++){
for(int i=j-1;i>=0;i--){
if(s[i]==s[j]) a[i][j]=a[i+1][j-1]+2;
else a[i][j]=max(a[i+1][j],a[i][j-1]);
}
}
return a[0][n-1];
}
};我们再思考一下：如果是要求连续的？
我们用bool数组f[i][j]表示i---j是否为回文
转移方程：if a[i]==a[j]&&f[i+1][j-1]==1回文，反之不回文
下面看一个具体应用：
我们先不考虑它成环，我们令dp[i][j]为i---j的合并的max,那么我们枚举最后一次合并的分界+i---j的和即可，转移方程为dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
我们再考虑成环，其实只是断开点的不同，换句话说，1234的情况变成了1234，2341，3412，4123,我们只要取max即可，为方便同时利用上一次的记入，我们直接for12341234即可。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,dp[402][402],dp1[402][402],a[402],sum[402];
int f(int i,int j){
if(i==j) return dp[i][j]=0;
if(dp[i][j]!=-1) return dp[i][j];
for(int k=i;k<=j-1;k++){
dp[i][j]=max(dp[i][j],f(i,k)+f(k+1,j)+sum[j]-sum[i-1]);
}
return dp[i][j];
}
int f1(int i,int j){
if(i==j) return dp1[i][j]=0;
if(dp1[i][j]!=-1) return dp1[i][j];
dp1[i][j]=f(i+1,j)+sum[j]-sum[i-1];
for(int k=i;k<=j-1;k++){
dp1[i][j]=min(dp1[i][j],f1(i,k)+f1(k+1,j)+sum[j]-sum[i-1]);
}
return dp1[i][j];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=2*n;i++){
a[i]=a[i-n];
sum[i]=sum[i-1]+a[i];
}
memset(dp,-1,sizeof(dp));
memset(dp1,-1,sizeof(dp1));
int ans1=0,ans2=f1(1,n);
for(int i=1;i<=n;i++){
ans2=min(ans2,f1(i,i+n-1));
}
cout<<ans2<<endl;
for(int i=1;i<=n;i++){
ans1=max(ans1,f(i,i+n-1));
}
cout<<ans1<<endl;
}
