动态规划（DP）各类模板题小结

dp，大致是分为求最长连续子序列的和，最长非递减子序列，最长公共子序列，最长回文子串这几大类题目，这些题目，都大致的讲了一下dp的思想，对于一些正规的比赛的题目来说，个人认为还是掌握dp的思想是很重要的。毕竟，万变不离其宗嘛。

最大连续子序列的和

比较朴素的方法就是通过求两个for循环，枚举两个端点，然后通过计算该区间的端点之间的数之和，这样下来的时间复杂度就是n^3,数据量大的数据肯定是不适合的。而且，就算是利用前缀和来进行解题的话，先扫一边数据，然后记录数据的前缀和，然后再利用for循环来进行枚举两个端点的话，其时间复杂度也有N^2,这样看来应该要另寻出路了。我们拿到这个题目的时候，我们的想法就是选择一个连续的子序列，然后这个子序列的和是最大的。然后肯定是无从下手的。但是，我们转念一想，如果我们遍历到了某一个位置的时候，我们已经知道在这个位置之前的最大的连续子序列的和的话，也就是已经知道了这个子序列的以前一个位置结尾的最大的子序列的和的话，那么我们在遍历这个位置的时候，我们就可以通过比较以这个位置结尾连续子序列的和的值，与当前值的大小，然后，用一个数组记录这个值，当作最大值，这样下来，我们就可以利用这个原理，在遍历完所有的数据之后，最后那个得到的就是我们要求的。也就是可以利用一个数组dp，dp[i]表示的是以当前下标i结尾的最大的连续子序列的和，然后在遍历到每一个位置的时候，我们可以比较dp[i-1]+a[i]与a[i]的大小，然后将更大的值记录在dp[i]里面，最后所得到的dp[n]就是我们要求的答案了。

公式：dp[i]=max(dp[i-1]+a[i],a[i])

代码：

#include<iostream> 
using namespace std;
int a[1000010];
int dp[1000010];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)  cin>>a[i];
    dp[0]=a[0];
    for(int i=1;i<n;i++){
        dp[i]=max(dp[i-1]+a[i],a[i]);
    }
    int ans=1e-9;
    for(int i=0;i<n;i++)  ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}

最长非递减子序列(LIS)

我们要在一个数组里面求一个非连续的最长的子序列的长度。这个题目的话，朴素的方法就是枚举每个数组中的元素，然后利用选或者不选这个元素来记录下最长的长度。显然，复杂度就是2^N,这是难以接受的。
我们可以转化另一种思想，我们可以通过这个一个数组来记录某个位置的之前的最长的非递减子序列的长度，数组的最后一个元素就是我们要求的答案了。
dp[i]表示的是在下标为i的位置之前的最长的非递减的子序列的长度，利用两个for循环，在到达某一个位置的时候，我们可以从头遍历到这个位置，然后寻找这个过程之中出现的最大的非递减的子序列的长度，最后更新这个长度为dp[i]即可，时间复杂度为N^2。

公式：if(a[i]>=a[j]&&dp[j]+1>dp[i])  dp[i]=dp[j]+1

代码：

#include<iostream>
using namespace std;
int a[1000];
int dp[1020];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)  cin>>a[i];
    int ans=-1;
    for(int i=0;i<n;i++){
        dp[i]=1;
        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<<endl;
    return 0;
}

最长公共子序列（LCS）

题目给我们两个字符串，然后我们要求出两个字符串的最大的公共部分（可以不连续，但是顺序不能改变），比较暴力的一种方法就是通过两个字符串的选和不选的区别，然后得到两个字符串，然后计算这两个字符串是否相同，时间复杂度为2^(N+M)*(NXM),时间复杂度之大可想而知。
dp的思路，就是开一个二维数组，然后利用二维数组来表示两个字符串的某一个位置的目前得知的最大的公共部分的长度，这样下来的话，可以通过一个for循环，我们每到一个位置的时候，就可以比较两个字符串的最大的公共的子序列的长度，然后就可以最后得出所求的答案。
dp[i][j]表示的是在字符串a遍历到i位置的时候，在字符串b遍历到j位置的时候，我们的已知的最长的公共子序列的长度。我们每到i，j位置，就比较a[i]和b[j]的字符是否相同，如果相同的话，那么就更新dp[i][j]为dp[i-1][j-1]+1,否则，那么就可以将i，j位置的最长的公共子序列转换为i-1，j位置和i，j-1位置的最大的那一个。

公式：if(a[i]==b[j])  dp[i][j]=dp[i-1][j-1]+1;
else  dp[i][j]=max(dp[i-1][j],dp[i][j-1])

C语言代码：

#include<iostream>
#include<cstring>
using namespace std;
char a[120],b[120];
int dp[120][120];
int main(){
    gets(a+1);
    gets(b+1);
    int len1=strlen(a+1);
    int len2=strlen(b+1);
    for(int i=0;i<=len1;i++)  dp[i][0]=0;
    for(int j=0;j<=len2;j++)  dp[0][j]=0;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(a[i]==b[j])  dp[i][j]=dp[i-1][j-1]+1;
            else  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[len1][len2]<<endl;
    return 0;
}

C++代码：

#include<iostream>
#include<string>
using namespace std;
int dp[120][120];
string a,b;
int main(){
    cin>>a>>b;
    int len1=a.size();
    int len2=b.size();
    for(int i=0;i<len1;i++){
        if(a[i]==b[0])   dp[i][0]=1;
        else  dp[i][0]=0;
    }
    for(int j=0;j<len2;j++){
        if(a[0]==b[j])  dp[0][j]=1;
        else  dp[0][j]=0;
    }
    int ans=-1;
    for(int i=1;i<len1;i++){
        for(int j=1;j<len2;j++){
            if(a[i]==b[j])  dp[i][j]=dp[i-1][j-1]+1;
            else  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<dp[len1-1][len2-1]<<endl;
    return 0;
}

最长回文字串

最长回文字串就是给我们一个字符串，然后我们要找出这个字符串里面的最长的回文子串的长度。对于这个类型的题目，还是先暴力的方法，最长的回文子串，就是枚举长度（也就是用一个for循环枚举区间的两个端点，然后超出这个长度的所有的子串，判断是否为回文子串，这样的复杂度就是N^3。
对于dp的做法，我们可以利用一个二维数组来判断当前的从i到j位置的是否为回文字符串，如果是dp[i][j]为1，否则为0，这样下来的话,对于两个位置，我们只需要判断这两个字符串是否相等，如果相等的话，我们就要dp[i][j]=1。我们看这个，我们是从大区间往小区间推的，但是，我们不知道小区间的dp的情况，这样下来，显然就很难继续进行递推下去了。那么，我们可以反其道而行之，我们可以从小长度往大长度进行递推，我们知道，对于小长度的为1的，肯定是回文子串，然后对于小长度为2的，我们只需要判断相邻的两个字符是否相等，如果相等，那么就将它置为1，否则为0，我们求到两个长度的回文子串的时候，因为两个以下的字符串之间没有字符了，故不能进行状态转移。我们就可以将状态进行转移了。我们枚举回文子串可能的长度，对于每个长度，我们枚举他们的边界，然后记录最长的ans。

公式：if(s[i]==s[j]&&dp[i+1][j-1]==1)  dp[i][j]=1;

代码：

#include<iostream>
using namespace std;
int dp[120][120];
string s;
int main(){
    cin>>s;
    int len=s.size();
    int ans=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;
            }
        }
    }
    for(int l=3;l<=len;l++){
        for(int i=0;i<len;i++){
            int j=i+l-1;
            if(s[i]==s[j]&&dp[i+1][j-1]){
                dp[i][j]=1;
                ans=l;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}