最长不下降子序列（LIS）（动态规划）

   

• 状态设计：dp[i]表示以str[i]结尾的最长不下降子序列长度
•     状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）；
•     当然，后面我们还可以输出这个最长不下降子序列的内容，只需要从后面开始枚举dp的值进行递减，只要dp的值与temp(最长子序列长度递减)相等， 就把str[i]的值加到lis中，直到temp==0为止。
•     输出第一个最长不下降子序列的内容呢：不过是从前面开始枚举罢了。

/**
    2)状态设计：dp[i]表示以str[i]结尾的最长不下降子序列长度
    状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）；
    当然，后面我们还可以输出这个最长不下降子序列的内容，只需要从后面
    开始枚举dp的值进行递减，只要dp的值与temp(最长子序列长度递减)相等，
    就把str[i]的值加到lis中，直到temp==0为止。
    输出第一个最长不下降子序列的内容呢：不过是从前面开始枚举罢了。
*/

/**
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len],ans=0;  //dp[i]表示以str[i]结尾的最长不下降子序列长度
    dp[0]=1;            //状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）

    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        }
        ans=max(ans,dp[i]);
    }
    string lis; //lis输出最长不下降子序列
    int temp=ans;
    for(int i=len-1;i>=0;--i)
    {
        if(dp[i]==temp)
        {
            lis=str[i]+lis;   temp从后开始往前寻找结果，当最长不下降序列
            --temp;           不止一个结果时，得到的序列是最后一组
        }
    }
    cout << ans << endl;
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    cout << lis << endl;
    string first;
    temp=1;
    for(int i=0;i<len;++i)
    {
        if(dp[i]==temp)
        {
            first+=str[i];
            ++temp;
        }
    }

    cout << "first substr:\n";
    cout << first << endl;
    return 0;
}
*/

3)为了后续不下降子序列的内容进行输出，也可开一个result数组，result[i]
    表示str[i]的前继结点，一个序列的首结点设置为-1，与其他节点进行区分，
    其实和第一个程序利用dp的值进行输出内容是一样的。

/**
    3)为了后续不下降子序列的内容进行输出，也可开一个result数组，result[i]
    表示str[i]的前继结点，一个序列的首结点设置为-1，与其他节点进行区分，
    其实和第一个程序利用dp的值进行输出内容是一样的
*/

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cout << "input a string:\n";
    cin >> str;
    int len=str.size();
    int dp[len];        //dp[i]表示以str[i]结尾的最长不下降子序列长度
    dp[0]=1;            //状态转移方程：dp[i]=max(dp[j]+1,1)   （j<i&&str[j]<=str[i]）
    int result[len];    //result[i]表示str[i]的前继结点
    result[0]=-1;       //一个序列的首结点设置为-1，与其他节点进行区分
    for(int i=1;i<len;++i)
    {
        dp[i]=1;
        result[i]=-1;
        for(int j=0;j<i;++j)
        {
            if(str[j]<=str[i]&&dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                result[i]=j;
            }
        }
    }
    int p=0,imax=0;
    for(int i=0;i<len;++i)
    {
        if(dp[i]>imax)
        {
            imax=dp[i];
            p=i;
        }
    }
    string lis;
    for(;p!=-1;)
    {
        lis=str[p]+lis;
        p=result[p];
    }
    cout << imax << endl;
    cout << lis << endl;
    cout << "调试:\n";
    for(auto a:str)
        cout << a << ' ';
    cout <<  endl;
    for(auto a:dp)
        cout << a << ' ';
    cout << endl;
    for(auto a:result)
        cout << a << ' ';
    cout << endl;
    return 0;
}