动态规划

最大连续子列和


在一组连续的数字序列中 A1 ~ An中求得一个从Ai ~ Aj的序列,使得该序列的和最大,求此最大和的问题成为最大连续子列和。

  使用一个dp数组记录子问题的结果,其中dp[i]表示以A[i]作为结尾的连续子的最大和(A[i]必须是这个序列的结尾),则dp[i]的获得有以下两种方法:
  一、该序列只有A[i]开始,A[i]结束,所以其dp[i]值为A[i];
  二、该序列从A[p]其中( p < i ) 开始一直到A[i]结束,测试dp[i]的值等于dp[i-1]+A[i];
  由此变得出动态规划的递推关系,即状态转移方程:

dp[i]=max(A[i],dp[i-1]+A[i]);

  在更新dp[i]的时候更新最大值,或者到dp数组求解完成后遍历一遍dp数组得到最大值,便是最大连续子列和,其代码实现如下:

#define MAXN 1000
#define INF 0x3fffffff
int A[MAXN],dp[MAXN];               //A数组存放原始数据序列
int main(){
    int n;
    cin>>n;
    int maxsum=-INF
    for(int i=0;i<n;i++){
        cin>>A[i];
        if(i==0)    dp[0]=A[0];     //初始化dp[0]为第一个元素
        if(i>0)
            dp[i]=max(A[i],dp[i-1]+A[i]);
        if(dp[i]>maxsum)
            maxsum=dp[i];
    }
    cout<<maxsum;
    return 0;
}

  显然很容易发现这个题目,可以省去dp数组,直接在每一步进行判定,每次更新当前的dp值时,只用到之前的一个的数据,因此更靠前的结果便不必保存,这样的算法也称为在线处理

最长不下降子序列(LIS)


在一个数字序列中,找到一组最长的子序列(可以连续,也可以不连续),使得这个子序列是非递减的,输出这个最长子序列的长度。

  使用dp数组记录子问题的结果,dp[i]记录以A[i]结尾的最长不下降子列的长度,那么对于dp[i]的获得,有以下方法:
  一、如果在元素A[i]之前存在一个元素A[j]是的A[i]>=A[j]并且dp[j]+1>dp[i],那么说明A[i]加入到以A[j]结束的最长不下降子序列中能够形成更长的LIS,因此更dp[i]=dp[j]+1;
  二、如果A[i]之前的元素都比A[i]大,则其自身形成一个LIS,该序列中只有A[i]自己,因此长度为1;
  由此,也能得到求解dp[i]时候的递推关系,即状态转移方程

dp[i]=max(1,dp[j]+1);       //其中j是A[i]能够加入形成更长的LIS情况

  其代码实现如下:  

#define MAXN 1000
int A[MAXN],dp[MAXN];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){                   //输入数据
        cin>>A[i];
    }
    int ans=-1;
    for(int i=1;i<n;i++){                   //从第二个元素开始更新dp数组
        dp[i]=1;                            //初始化为1,即只有自己构成LIS的情况
        for(int j=0;j<i;j++){               //从头寻找是否有更优的解
            if(A[i]>=A[j]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
        ans=max(ans,dp[i]);                 //更新并记录最优解
    }
    cout<<ans;
    return 0;
}

最长公共子序列(LCS)


给定两个字符串或者数字序列,A和B,求A和B最长的公共子序列的长度(子序列可以不连续)。

  使用一个二维的dp数组记录子问题的结果,dp[i][j]表示A的i号位置和B的j号位置之前(包含i和j位)的LCS长度,则求解dp[i][j]的时候有以下情况:
  一、如果A[i]==B[j]则字符串的的LCS就增加一位,dp[i][j]=dp[i-1][j-1]+1;
  二、如果A[i]!=B[j],这时无法使得LCS更长。因此dp[i][j]需要继承dp[i-1][j]和dp[i][j-1]中较大的值,也就是前一个最长的LCS的数值。
  由此得到求解dp[i][j]时候的递推关系,即状态转移方程

A[i]==B[j]时,dp[i][j]=dp[i-1][j-1]+1;
A[i]!=B[j]时,dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

  其代码实现如下:

#define MAXN 1000
char A[MAXN],B[MAXN];
int dp[MAXN][MAXN];
int main(){
    int n;
    cin>>n;
    gets(A+1);                  //为了更容易判断,从下标1开始存储字符串
    gets(B+1);
    int lena=strlen(A+1),lenb=strlen(B+1);
    for(int i=0;i<=lena;i++){   //初始化边界值
        dp[i][0]=0;
    }
    for(int i=0;i<=lenb;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=lena;i++){
        for(int j=1;j<lenb;j++){
            if(A[i]==B[i])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[lena][lenb];       //输出最终结果
}

最长回文子串


最长回文子串问题要解决给定的一个字符串的最长回文子串的长度。

  对于一个字符串S来说,使用dp[i][j]表示字符串i到j位置是不是一个回文串(用1表示是,0表示不是),则求解dp[i][j]时可分为一下两种情况:
  一、如果S[i]==S[j],如果S[i+1]到S[j-1]是回文串则S[i][j]也是回文串,否则不是回文串。
  二、如果S[i]!=S[j],那么S[i]到S[j]一定不是回文串。
  由此,可以得到求解dp[i][j]时候的递推关系,即状态转移方程

S[i]==S[j],dp[i][j]=dp[i+1][j-1];
S[i]!=S[j],dp[i][j]=0;

  其代码实现过程如下:

#define MAN 1000
char s[MAXN];
bool dp[MAXN][MAXN]={0};
int main(){
    gets(s);
    int len=strlen(s),ans=1;                    //初始化答案为1,至少有一位
    //状态边界
    for(int i=0;i<len;i++){
        dp[i][i]=1;
        if(i<len-1){
            if(s[i]==s[i+1]){
                dp[i][i+1]=1;
                ans=2;                          //如果有两位相邻且相同的,则答案至少为2
            }
        }
    }
    //求解dp
    for(int L=3;L<=len;L++){                    //枚举字串的长度
        for(int i=0;i+L-1<len;i++){             //枚举字串的起始端点
            int j=i+L-1;                        //计算字串的右端点
            if(s[i]==s[j&&dp[i+1][j-1]==1]){    //状态转移方程
                dp[i][j]=1;
                ans=L;
            }
        }
    }
    cout<<ans;
    return 0;
}

当珍惜每一片时光~