大家好，今天我想写一篇关于线性dp的题解，主要是今天刚学（普及1第八讲），而且csp比赛中经常用到。我上次违反了论坛相关规则，我这次会注意的(主要多讲思路)。
1.先来明确一下线性dp的定义： 线性DP就是指状态的转移具有线性递推关系，每个状态只依赖之前的状态，按照线性顺序一步步递推下去。
正如之前在背包问题中所写到的，仍旧可以用状态表示和状态计算来解决。
2.线性dp相关题目：
(1).最长上升子序列问题
这道题的思路较好理解，编码也十分简洁。
思路讲解：
我们可以用dp[i]来存储答案，对于一个dp[i]，
我们可以将其定义为以bi为结尾的最长的最长上升子序列。
接下来我们要理解一个性质：
我们所称的递增是元素的大小递增，以及元素的下标递增。
所以就意味着对于一个数b[i]可以放在b[1~i-1]这几个位置后面，同时满足b[i]>b[j],这样我们就可以推导出状态转移方程
dp[i]=max(dp[i],dp[j]+1);
主要代码如下
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
呵呵，这样就AC了！！！交上去会看见只得了10分
那么这是为什么呢？，实际上我们掉入了一个大坑之中，大家仔细想一想，如果说对于一个元素b[i],前面的每个元素都是大于b[i],这样我们的dp数组当中的dp[i]=0了，但是实际上因该为1。
遇到这种情况我们怎么办呢？其实可以当每次访问到dp[i]时，dp[i]最初就设为1。
于是代码是这样的
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
这样我们就真的AC了。这次是真的！
2.最长公共子序列
思路和代码先不讲了，因为实在太晚了，有时间会补的。
先放一张图示（自己先理解吧！）：
本次的讲解先到这里，由于水平属实得太菜，有误请包容。