发布时间：2025-06-24 19:49:51  作者：北方职教升学中心  阅读量：309

对于数组中的每个元素a[i]，我们遍历所有在它之前的a[j]（即j < i），找到所有小于a[i]的元素，并更新dp[i]为max(dp[j] + 1,dp[i])，其中j满足a[j] < a[i]。

        最优子结构的含义：在最长公共子序列问题中，最优子结构意味着原问题的最优解可以通过求解其子问题的最优解来构建。这样，最终dp数组中的最大值就是最长递增子序列的长度。这种方法中，我们维护一个数组end，其中end[i]表示长度为i+1的递增子序列的最小结尾元素。此时，我们可以确定c[i][j]等于c[i-1][j-1] + 1。然后说明如何只用min(m,n)个表项及O(1)的额外空间完成相同的工作。

#include <string>#include <iostream>#include <vector>using namespace std;int LIS_LENGTH(string X){    int n = X.length();    int Max_len=-1;    vector<int> dp(n, 1);    if (X.empty())        return 0;    else    {        for (int i = 1; i < n; i++)        {            for (int j = 0; j < i; j++)            {                if (X[i] > X[j])                {                    dp[i] = max(dp[i], dp[j] + 1);                }            }            Max_len = max(Max_len, dp[i]);        }    }    return Max_len;}int main(){    string X = "571946283";    cout<<LIS_LENGTH(X);    return 0;}

4.2 O(nlogn)时间复杂度

        二分查找优化的动态规划：为了优化动态规划中的时间复杂度，可以使用二分查找来减少寻找合适a[j]的时间。

根据算法导论中给出的方法实现最长公共子序列（备忘录技术，c[i][j]就相当于是我们的备忘录），但是这种方法不能给出所有相同长度最长子序列的情况： 

#include <string>#include <iostream>using namespace std;string X, Y;int c[51][51];char b[51][51];void LCS_LENGTH(string X, string Y){    int m = X.length();    int n = Y.length();    for (int i = 1; i <= m; i++)        c[i][0] = 0;    for (int j = 0; j <= n; j++)        c[0][j] = 0;    for (int i = 1; i <= m; i++)    {        for (int j = 1; j <= n; j++)        {            if (X[i - 1] == Y[j - 1])            {                c[i][j] = c[i - 1][j - 1] + 1;                b[i][j] = '|'; //↖:直接输入这个符号程序无法识别            }            else if (c[i - 1][j] >= c[i][j - 1])            {                c[i][j] = c[i - 1][j];                b[i][j] = '<'; //↑            }            else            {                c[i][j] = c[i][j - 1];                b[i][j] = '>'; //←            }        }    }}void Print_LCS(string X, int i, int j){    if (i == 0 || j == 0)        return;    if (b[i][j] == '|')    {        Print_LCS(X, i - 1, j - 1);        cout << X[i - 1];    }    else if (b[i][j] == '<')        Print_LCS(X, i - 1, j);    else        Print_LCS(X, i, j - 1);}int main(){    X = "ABCBDAB";    Y = "BDCABA";    LCS_LENGTH(X, Y);    Print_LCS(X, X.length(), Y.length());    return 0;}

• 数据结构的选择：在解决最长公共子序列问题时，通常会使用二维数组c[ ][ ]来记录最长公共子序列的长度，以及另一个二维数组b[ ][ ]来记录这些长度的来源；
• 初始化过程：对于给定的两个字符串s1和s2，我们会将c[ ][ ]的第一行和第一列初始化为0，这代表空字符串与任何字符串的最长公共子序列长度为0；
• 递归关系的建立：我们用c[i][j]来记录序列Xi（即s1的前i个字符）和Yj（即s2的前j个字符）的最长公共子序列的长度。

  1.一般的动态规划

  解题依据：

          最长公共子序列问题的最优子结构性质，是指在两个序列的最长公共子序列中，如果最后一个字符相同，则这个相同的字符一定是最长公共子序列的最后一个字符，并且剩余部分也是这两个序列去掉最后一个字符后的最长公共子序列。动态规划通过存储这些子问题的结果来避免重复计算，从而提高效率，即使用‘备忘录’技术。当i=0或j=0时，最长公共子序列的长度为0，因为至少有一个序列是空的；

• 最优子结构的分析：如果Xi和Yj的最后一个字符相同，那么这个字符一定包含在它们的最长公共子序列中。

  #include <string>#include <iostream>#include <vector>using namespace std;int LIS_LENGTH(vector<int> X){    if (X.empty())        return 0;    int n = X.size();    vector<int> end(n);    end[0] = X[0];    int L = 0;    int R = 0;    int left = 0;    int right = 0;    int Max_len = 1;    for (int i = 1; i < n; i++)    {        L = 0;        R = right;        //在这里使用二分查找，可以查找到大于等于X[i]最左边的位置        while (L <= R)        {            int mid = (L + R) / 2;            if (X[i] > end[mid])                L = mid + 1;            else                R = mid - 1;        }        right = max(right, L);//right可能出现-1，即X[i]落在了end数组第一个元素的左边        Max_len = max(Max_len, L+1);//X[i]落在end的数组右边，需要更新Max_len的大小        end[L] = X[i];    }    return Max_len;}int main(){    vector<int> X = {1,4,7,5,6};    cout<<LIS_LENGTH(X);    return 0;}

  参考书籍：《算法导论》——托马斯·科尔曼

  参考文章1：http://t.csdnimg.cn/6qIln

  参考文章2：http://t.csdnimg.cn/wGkos

  参考文章3：http://t.csdnimg.cn/xlQKj  

  ---

         喜欢的小伙伴还请点赞收藏，(❁´◡`❁)(　o=^•ェ•)o　┏━┓

  ---