線性動態規劃基礎，線性動態規劃

線性動態規劃基礎，線性動態規劃

最大子段和：

dp[0]=a[0];
for(int i=1; i<n; i++)
{
　　if(dp[i-1]>0)
　　　　dp[i]=dp[i-1]+a[i];
　　else
       dp[i]=a[i];
}

最長遞增子序列：

#include <iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
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 <iostream>
#include <cstdio>
#include <string>
#include <cstring>
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);
}