动态规划，是用于解决一类最优化问题的算法思想。简单来说，将一个复杂的问题分解成若干个子问题，通过子问题的最优解推出原问题的最优解，动态规划会记录子问题的结果，用于求解最终问题，解决了纯粹使用递归时候重复计算的问题。这里总结几种常见的动态规划问题及其算法。

目录

动态规划

最大连续子列和

　　使用一个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）

　　
　　使用一个二维的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;
}