线性DP的几种模型和例题

  我们知道，动态规划用来解决一类最优化问题，通过将原问题分解成若干的子问题，并综合子问题的最优解从而得到原问题的最优解，线性DP就是这么一种现行的分析DP的思路。

  我们这里来介绍几种常见的模型以及例题：

  1.数字三角形模型

   例题：898. 数字三角形 - AcWing题库

    状态表示：

   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.最长上升子序列

   例题：895. 最长上升子序列 - AcWing题库

    这道题由于数据范围只有1000，所以我们可以用O（n^2）的时间复杂度来解决

    状态表示：f[i]表示的是以q[i]为结尾的最长上升子序列（所以我一共得扫两次数列q）

    状态计算：循环就好了，但是最大值不一定是f[i]，需要再扫一遍找到最大值

  变形：将数据范围提升至1≤N≤100000">1≤N≤100000

1≤N≤100000">  例题：896. 最长上升子序列 II - AcWing题库

1≤N≤100000">  很明显，超时了。所以我们需要来优化算法，但是这样优化就已经不太像是DP了，反而有点贪心的味道；

1≤N≤100000"> 

1≤N≤100000">  分析：我们先用暴力的方法找到这道题怎么思考，什么时候能够让当前序列增长呢？  当我们发现新来的这个点q[i]比前一个子序列的最后一个值大，那么长度len加一；  

1≤N≤100000">  我们发现这里很关键的几个点是：当前遍历到的点q[i]，前一个子序列的最后一个值，序列长度。  其中q[i]是我们在循环中遍历的，所以需要记录的点有两个，一个是序列长度，一个是序列最后一个值，所以我们可以考虑以长度作为下标存储序列最后一个值。

1≤N≤100000">  并且我们可以发现，随着长度的不断增长，序列的最后一个值只会更大，所以这个长度是我们可以二分的依据，这样的话时间复杂度就变成了O（nlogn）。

1≤N≤100000">  这样看起来，仿佛已经可行了，让我们在证明一些情况，f[r]的值可能会被更新 ， 比如序列 1 ，2 ， 8 ， 4 ， 5；  我们可以发现f[3]一开始是8，但是因为4，比f[2]，也就是2大，所以可以更新f[3]为4，为什么可以更新呢，因为能够使len增加的关键在于遍历的点的后面，前面的的点已经贡献完了，没有作用了，所以不必担心被更新后造成影响。  

1≤N≤100000">  这里怎么样能让len增加呢，就是不断地发现后面的点能够更新，直到q[i] > f[len]，此时len就得增加了。

1≤N≤100000">  二分搜索的是，长度最长的且序列最后一位小于q[i]的。

1≤N≤100000">··············暂时休息一下···················

1≤N≤100000">··············继续看别的模型················

1≤N≤100000">  3.最长公共子序列

1≤N≤100000">  例题：897. 最长公共子序列 - AcWing题库

1≤N≤100000">

    状态表示：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.最短编辑距离

  例题：902. 最短编辑距离 - AcWing题库

   状态表示：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);