您當(dāng)前位置：首頁(yè) > php開(kāi)源 > 綜合技術(shù) > 動(dòng)態(tài)規(guī)劃總結(jié)【模板】

動(dòng)態(tài)規(guī)劃總結(jié)【模板】

來(lái)源：程序員人生發(fā)布時(shí)間：2015-07-08 08:04:59 閱讀次數(shù)：4545次

最長(zhǎng)遞增子序列

給定1個(gè)序列，找到最長(zhǎng)子序列的長(zhǎng)度，使得子序列中的所有元素被排序的順序增加。

1.求最長(zhǎng)遞增子序列的長(zhǎng)度O(N^2)

int Arr[30010],List[30010];
int LIS(int *Arr,int N)    //arr[]寄存的是待求數(shù)組
{
    int Max = 0;        //max為最大遞增子序列的長(zhǎng)度
    for(int i = 1; i <= N; ++i)
        List[i] = 1;    //lis[i] 寄存i之前的最大遞增子序列的長(zhǎng)度，初始都為1

    for(int i = 2; i <= N; ++i)
        for(int j = 1; j < i; ++j)    //遍歷i之前所有位置
            if(Arr[i] >= Arr[j] && List[i]<List[j]+1)
                List[i] = List[j] + 1;
            //arr[i]>arr[j]為遞增
            //lis[i]<lis[j] + 1確保為當(dāng)前最長(zhǎng)遞增序列

    for(int i = 1; i <= N; ++i)
        if(Max < List[i])
            Max = List[i];

    return Max;
}

2.求最長(zhǎng)遞增子序列的長(zhǎng)度O(NlogN)

int Arr[10010],List[10010];
int Stack[10010];
int LIS(int *Arr,int N)
{
    int top = 0;
    Stack[top] = -1;
    for(int i = 1; i <= N; ++i)
    {
        if(Arr[i] > Stack[top])
            Stack[++top] = Arr[i];
        else
        {
            int low = 1;
            int high = top;
            while(low <= high)
            {
                int mid = (low + high)/2;
                if(Arr[i] > Stack[mid])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            Stack[low] = Arr[i];
        }
    }
    return top;
}

最長(zhǎng)公共子序列

給定兩個(gè)序列，找出在兩個(gè)序列中同時(shí)出現(xiàn)的最長(zhǎng)子序列的長(zhǎng)度。1個(gè)子序列是出現(xiàn)在相對(duì)順序的序列，但不1定是連續(xù)的。

1.求最長(zhǎng)公共子序列長(zhǎng)度

char s1[220],s2[220];
int dp[220][220];
//求串s1和串s2的公共子序列
int lcs(char *s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    for(int i = 0; i <= len1; ++i)
    {
        for(int j = 0; j <= len2; ++j)
        {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else if(s1[i-1] == s2[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[len1][len2];
}

2.求最長(zhǎng)公共子序列長(zhǎng)度，并輸前途徑

int dp[110][110],pre[110][110],len1,len2;
char s1[110],s2[110];

void LCS(char *s1,char *s2)
{
    for(int i = 0; i <= len1; ++i)
        pre[i][0] = 1;
    for(int i = 0; i <= len2; ++i)
        pre[0][i] = 2;
    //得到最長(zhǎng)公共子序列，并標(biāo)記dp[i][j]的上1個(gè)狀態(tài)，用來(lái)回溯尋覓路徑
    for(int i = 0; i <= len1; ++i)
    {
        for(int j = 0; j <= len2; ++j)
        {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                pre[i][j] = 0;
            }
            else if(dp[i-1][j] >= dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
                pre[i][j] = 1;
            }
            else
            {
                dp[i][j] = dp[i][j-1];
                pre[i][j] = 2;
            }
        }
    }
}

void Print(int i,int j) //回溯輸出新的字符串序列
{
    if(i == 0 && j == 0)
        return ;
    if(pre[i][j] == 0)
    {
        Print(i-1,j-1);
        printf("%c",s1[i-1]);
    }
    else if(pre[i][j] == 1)
    {
        Print(i-1,j);
        printf("%c",s1[i-1]);
    }
    else
    {
        Print(i,j-1);
        printf("%c",s2[j-1]);
    }
}

void solve(char *s1,char *s2)
{
    len1 = strlen(s1);
    len2 = strlen(s2);
    LCS(s1,s2);
    Print(len1,len2);
    printf("
");
}

最長(zhǎng)回文子序列

給1個(gè)字符串，找出它的最長(zhǎng)的回文子序列LPS的長(zhǎng)度。例如，如果給定的序列是“BBABCBCAB”，則輸出應(yīng)當(dāng)是7，“BABCBAB”是在它的最長(zhǎng)回文子序列。

char s[2020];
int dp[2020][2020];
//dp[i][j]表示s[i~j]最長(zhǎng)回文子序列
int LPS(char *s)
{
    memset(dp,0,sizeof(dp));
    int len = strlen(s);
    for(int i = len⑴; i >= 0; --i)
    {
        dp[i][i] = 1;
        for(int j = i+1; j < len; ++j)
        {
            if(s[i] == s[j])    //頭尾相同，最長(zhǎng)回文子序列為去頭尾的部份LPS加上頭和尾
                dp[i][j] = dp[i+1][j⑴] + 2;
            else    //頭尾不同，最長(zhǎng)回文子序列是去頭部份的LPS和去尾部份LPS較長(zhǎng)的
                dp[i][j] = max(dp[i][j⑴],dp[i+1][j]);
        }
    }

    return dp[0][len⑴];
}

最小編輯距離

給定1個(gè)長(zhǎng)度為m和n的兩個(gè)字符串，設(shè)有以下幾種操作：替換（R），插入（I）和刪除（D）且都是相同的操作。尋覓到轉(zhuǎn)換1個(gè)字符串插入到另外一個(gè)需要修改的最?。ú僮鳎?shù)量。

int dp[1010][1010],len1,len2;
char s1[1010],s2[1010];
int EditDist(char *s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
//當(dāng)兩個(gè)字符串的大小為0，其操作距離為0。
//當(dāng)其中1個(gè)字符串的長(zhǎng)度是零，需要的操作距離就是另外一個(gè)字符串的長(zhǎng)度. 
    for(int i = 0; i <= len1; ++i)
        dp[i][0] = i;
    for(int i = 0; i <= len2; ++i)
        dp[0][i] = i;

    for(int i = 1; i <= len1; ++i)
    {
        for(int j = 1; j <= len2; ++j)
        {
            if(s1[i-1] == s2[j-1])  //對(duì)齊s1[i⑴]和s2[j⑴]，不需改變
                dp[i][j] = dp[i-1][j-1];
            else    
                dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;
            //s1前綴右對(duì)齊,s2前綴右為' ',刪除s1第i個(gè)字符 -> dp[i⑴][j]
            //s2前綴右對(duì)齊,s1前綴右為' ',刪除s2第j個(gè)字符 -> dp[i][j⑴]
            //s1前綴右對(duì)齊,s2前綴右對(duì)齊,i、j不1樣，替換 -> dp[i⑴][j⑴]
        }
    }
    return dp[len1][len2];
}