LCS动态规划

相关笔记

思路

在给定的输入中寻找最优可能，可以通过动态规划实现。需要在一个未排序的序列中找到满足要求的最长序列，并输出最长序列长度。可以根据样例逐个值推导，发现每引入一个新的值时，最长序列的长度就可能+1，得到关系状态方程。

实现

1.输入：使用vector存放整数型的不定长数组，按照题目要求实现输入有点麻烦了。使用string将输入作为字符直接使用会更方便。
2.输出：dp数组存放的是各值作为新序列的最后一个值时序列的最大长度，因此需要对他们进行排序，找到最大的序列长度。
3.动态规划：外层的循环将原序列的每一个值进行遍历，内层的循环通过判断当前值和前面值的关系找到最长可能。判断的条件包括：当前值大于前面值，当前值具有的最大长度是目前最大的。

代码

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

vector<int> a;

int main()
{
    int i=0;
    do{
        cin>>i;
        a.push_back(i);
    }while(getchar()!='\n'); //输入
     
    int len=a.size();        
    int dp[len];
    for(int i=0;i<len;i++)  //dp[i]=(max+1(a[j]<a[i]&&dp[j]>max))
    {
        int max=0;
        for(int j=i;j>=0;j--)
            if(a[i]>a[j]&&dp[j]>max)
                max=dp[j];
        dp[i]=max+1;
    }

    sort(dp,dp+len);
    cout<<dp[len-1];        //输出 
}

总结

不仅是输入数字并按照大小排序时可使用这种方法，输入字母并按照字母顺序排序也可以使用。处理动态规划类题目时重要的一步是找到关系状态方程，确定状态方程后再想循环哪一个变量、循环中是否有判断条件、怎样实现等问题。
在理解之后这道题显得比较容易，但如果没有答案参考直接使用动态规划做的话会纠结很久。再做些动态规划的题目，让这个过程变熟悉些。