备战蓝桥杯---DP刷题1

话不多说，直接看题：

1.整数划分问题

题意很简单，就是求一个数被拆成n个数的方案，肯定有人说用隔板法，但是这里223与232被视为一个方案，但是隔板法就是认为这是两种情况，于是我们令f[i][j]表示分成j个数，当前值为i的方案数，那么我们如何转移？

有个比较妙的分法:

我们按照其选中的数最小值是否为0来分，对于最小值为0，那么就有f[i][j-1]，对于不是0的部分，他们最小值>=1，那么我们-1，问题就转化成了原问题即f[i-j][j],这样就得到转移方程了。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&m,&n);
        int f[N][N]={0};
        f[0][0]=1;
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=f[i][j-1];
                if(i>=j) f[i][j]+=f[i-j][j];
            }
        }
        cout<<f[m][n]<<endl;
    }
}

2.DP求回文：

首先我们把问题转化一下，我们贪心的想一想，脱离的就是不是该字符串中回文子串的个数，因此，问题就是求其最大回文子串，答案=字符数-最大回文子串，那么我们如何求？

我们令f[l][r]表示l--r上的最大回文子序列长度，我们考虑左右端点l,r，有4种情况,l,r为都在，那么f[l][r]=2+f[l+1][r-1]（s[l]=s[r])，l在，此时我们遇到一个问题，如何求右端点，若枚举复杂度超了，这里我们求f[l][r-1]即可，因为我们要求的答案一定在这个范围里，虽然会与其他答案有重复，但是不影响求最优解，其他情况同理，那么我们如何循环？可以无脑记忆化搜素，也可以按照先枚举长度再枚举端点来求，下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char s[N];
int f[N][N];
int main(){
    scanf("%s",s);
    int n=strlen(s);
    for(int len=1;len<=n;len++){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            if(len==1){
                f[l][r]=1;
            }
            else{
                if(s[l]==s[r]) f[l][r]=2+f[l+1][r-1];
                f[l][r]=max(f[l][r],f[l+1][r]);
                f[l][r]=max(f[l][r],f[l][r-1]);
            }
        }
    }
    cout<<n-f[0][n-1];
}

3.区间 DP：

就是求最大括号对，我们令f[i][j]表示将[i,j]变成合法括号序列的方案的集合的添加数量min,

对于f[i][j]，我们把它分为两种，第一种,()/[]型，第二种（）（）型，对于第一种，就是上一题，我们分为4类，i,j都被用上，i/j被用上。对于第二种，我们把它划分成第一种，我们不妨固定左端点，（）（）（）（）,我们分别枚举右括号（相当于枚举第一个括号的区间）对于（i,k)，答案为f[i][k](不一定是左右匹配的答案，但是属于包含关系，不影响最优解）。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110,INF=100000000;
int n;
int f[N][N];
bool mch(char l,char r){
    if(l=='('&&r==')') return 1;
    if(l=='['&&r==']') return 1;
    return 0;
}
int main(){
    string s;
    cin>>s;
    n=s.size();
    for(int len=1;len<=n;len++){
        for(int i=0;i+len-1<n;i++){
            int j=i+len-1;
            f[i][j]=INF;
            if(mch(s[i],s[j])) f[i][j]=f[i+1][j-1];
            f[i][j]=min(f[i][j],f[i][j-1]+1);
            f[i][j]=min(f[i][j],f[i+1][j]+1);
            for(int k=i;k<j;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
    }
    cout<<f[0][n-1];
}