先补充一下背包问题：

于是，我们把每一组当成一个物品，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;
}