线性动态规划基础-白红宇

线性动态规划基础

阅读量：6874 次

发布时间：2019-06-26

本文共 3828 字，大约阅读时间需要 12 分钟。

最大子段和：

dp[0]=a[0]; for(int i=1; i
     
      0)　　　　dp[i]=dp[i-1]+a[i];　　else       dp[i]=a[i]; }

dp[i]的值是从左至右包含a[i]的最大的子段和。dp[i]中最大的即整个串的最大的子段和。

最长公共子序列：

状态转移方程：

　　if(i==0 || j==0) dp[i,j]=0;

　　else if(X[i]==Y[j]) dp[i,j]= dp[i-1,j-1]+1;

　　else dp[i,j]= max(dp[i-1,j], dp[i,j-1]);

#include 
     
      #include
      
       #include 
       
        #include 
        
         using namespace std;const int MAX=1000;int dp[MAX][MAX]={
   0};int LCS( char *X, char *Y, int m, int n ){    for (int i=1; i<=m; i++)    {        for (int j=1; j<=n; j++)        {            if (X[i-1] == Y[j-1])                dp[i][j] = dp[i-1][j-1] + 1;            else                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);        }    }    return dp[m][n];}

最长回文串：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;//(dp)时间复杂度O(n^2),空间复杂度O(n^2)string LPS(string s){    const int len = s.size();    if(len <= 1)return s;    bool dp[len][len];    memset(dp, 0, sizeof(dp));    int resLeft = 0, resRight = 0;    dp[0][0] = true;    for(int i = 1; i < len; i++)    {        dp[i][i] = true;        dp[i][i-1] = true;//这个初始化容易忽略，当k=2时要用到    }    for(int k = 2; k <= len; k++)//枚举子串长度        for(int i = 0; i <= len-k; i++)//枚举子串起始位置        {            if(s[i] == s[i+k-1] && dp[i+1][i+k-2])            {                dp[i][i+k-1] = true;                if(resRight-resLeft+1 < k)                {                    resLeft = i;                    resRight = i+k-1;                }            }        }    return s.substr(resLeft, resRight-resLeft+1);}//时间复杂度O(n^2),空间复杂度O(1)string LPS2(string s){    const int len = s.size();    if(len <= 1)return s;    int start, maxLen = 0;    for(int i = 1; i < len; i++)    {        //寻找以i-1,i为中点偶数长度的回文        int low = i-1, high = i;        while(low >= 0 && high < len && s[low] == s[high])        {            low--;            high++;        }        if(high - low - 1 > maxLen)        {            maxLen = high - low -1;            start = low + 1;        }        //寻找以i为中心的奇数长度的回文        low = i- 1;        high = i + 1;        while(low >= 0 && high < len && s[low] == s[high])        {            low--;            high++;        }        if(high - low - 1 > maxLen)        {            maxLen = high - low -1;            start = low + 1;        }    }    return s.substr(start, maxLen);}

最长递增子序列

状态转移方程(O(n^2))：

　　dp[0]=1;

　　if(i<j && a[i]<a[j]) dp[i]=dp[j]+1;

O(nlogn):

　　B[i]记录的是最长递增子序列长度为i的序列的最小的末尾元素的值。

　　例如{1,6,4,9,5,7,8,6,8,9}；

　　则B[1]=1;

　　B[2]=[6];

　　由于4比6小，所以此时B[2]=4;此时长度为2的LIS的最小末尾元素是4;

　　B[3]=9;

　　B[3]=5;

　　B[4]=7;

　　B[5]=8;

　　由于6大于dp[3]小于B[4],所以此时B[4]=6;

　　B[5]=8;

　　B[6]=9;

　　LIS就为6，并且末尾最小的元素是9。

　　更改元素值是用二分，速度更快。

#include 
     
      #include 
      
       using namespace std;const int Max=10000;int dp[Max];// dp[j] = max(dp[i]) + 1int LIS_DP_N2(int *a, int n){    dp[0]=1;    for(int i = 1; i < n; i++)    {        int maxLen = 0;        for(int j = 0; j < i; j++)            if(a[i] > a[j])                maxLen=max(maxLen,dp[j]);        dp[i] = maxLen + 1;    }    int maxLIS = 0;    for(int i = 0; i < n; i++)    {        if(maxLIS < dp[i])            maxLIS = dp[i];    }    return maxLIS;}int BinarySearch(int *a, int value, int n){    int low = 0;    int high = n - 1;    while(low <= high)    {        int mid = (high + low) / 2;        if(a[mid] == value)            return mid;        else if(value
       
         B[nLISLen - 1])        {            B[nLISLen] = a[i];            nLISLen++;            Len[i]=nLISLen;        }        else        {            int pos = BinarySearch(B, a[i], nLISLen);            B[pos] = a[i];            Len[i]=pos+1;        }    }    return nLISLen;}