我们这里来介绍几种常见的模型以及例题：
- 数字三角形模型
状态表示：
f[i]j[j] 表示从顶点走到[i][j]这个点的最大距离；
状态计算：考虑能走到[i][j]这个点的两种方法，一种是从左上方来，一种是从右上方来，而这两者的最长距离已经计算，所以可以得到状态转移方程：
f[i][j] = max(f[i-1][j] + q[i][j] , f[i-1][j-1] + q[i][j] )
2.最长上升子序列
这道题由于数据范围只有1000，所以我们可以用O（n^2）的时间复杂度来解决
状态表示：f[i]表示的是以q[i]为结尾的最长上升子序列（所以我一共得扫两次数列q）
状态计算：循环就好了，但是最大值不一定是f[i]，需要再扫一遍找到最大值
变形：将数据范围提升至 1 ≤N ≤100000
很明显，超时了。所以我们需要来优化算法，但是这样优化就已经不太像是DP了，反而有点贪心的味道；
分析：我们先用暴力的方法找到这道题怎么思考，什么时候能够让当前序列增长呢？ 当我们发现新来的这个点q[i]比前一个子序列的最后一个值大，那么长度len加一；
我们发现这里很关键的几个点是：当前遍历到的点q[i]，前一个子序列的最后一个值，序列长度。 其中q[i]是我们在循环中遍历的，所以需要记录的点有两个，一个是序列长度，一个是序列最后一个值，所以我们可以考虑以长度作为下标存储序列最后一个值。
并且我们可以发现，随着长度的不断增长，序列的最后一个值只会更大，所以这个长度是我们可以二分的依据，这样的话时间复杂度就变成了O（nlogn）。
这样看起来，仿佛已经可行了，让我们在证明一些情况，f[r]的值可能会被更新 ， 比如序列 1 ，2 ， 8 ， 4 ， 5； 我们可以发现f[3]一开始是8，但是因为4，比f[2]，也就是2大，所以可以更新f[3]为4，为什么可以更新呢，因为能够使len增加的关键在于遍历的点的后面，前面的的点已经贡献完了，没有作用了，所以不必担心被更新后造成影响。
这里怎么样能让len增加呢，就是不断地发现后面的点能够更新，直到q[i] > f[len]，此时len就得增加了。
二分搜索的是，长度最长的且序列最后一位小于q[i]的。
··············暂时休息一下···················
··············继续看别的模型················
3.最长公共子序列
状态表示：f[i][j]代表的是A的前i个字符和B的前j个字符公共子序列的最长长度。
状态计算：可得到如下状态转移方程：
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
if(a[i] == b[j]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j]);
4.最短编辑距离
状态表示：f[i][j]表示字符串A的前i个字符和B的前j个字符编辑次数的最小值
状态计算：我们考虑会影响编辑次数的三个操作，增、删、改；
把当前的a[i]要进行的三种操作造成的后果进行枚举：
增：f[i][j] = f[i][j-1] + 1; 删：f[i][j] = f[i-1][j] + 1 ; 改: (a[i] == b[j] ) f[i][j] = f[i-1][j-1] (a[i] != b[j] ) f[i][j] = f[i-1][j-1] + 1;
状态转移方程如下：
dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1);
if(a[i] == b[j]) dp[i][j] = min(dp[i-1][j-1] ,dp[i][j]);
else dp[i][j] = min(dp[i][j] , dp[i-1][j-1] + 1);
Original: https://www.cnblogs.com/ZheyuHarry/p/16192362.html
Author: ZheyuHarry
Title: 线性DP的几种模型和例题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583582/
转载文章受原作者版权保护。转载请注明原作者出处！