【线性DP】模型总结

最长上升子序列

DP法

​ dp[i]表示以i结尾的最长上升子序列的长度。

​ 对于每个i，遍历j=1~i-1,若a[j] < a[i], 则dp[i] = max(dp[i], dp[j] + 1);

二分法

​ 可以优化时间复杂度。

​ dp[]数组用来存储当前最长上升子序列。

​ 若dp[]数组的最末尾的值小于当前原序列的值，则将这个值加入dp[]数组末尾。

​ 否则，使用Lower_bound找到dp[]数组中第一个大于该值的元素，替换。

​ 如果需要输出序列：定义s[]数组，记录下标，随dp[]数组更新。

最长公共子序列

​ 定义dp[] []二维数组，表示a串以i结尾，b串以j结尾的最长公共子序列。

​ 枚举i = 1 ~ a.size(), j = 1 ~ b.size().

​ 若a[i - 1] == b[j - 1], dp[i] [j] = dp[i - 1] [j - 1] + 1;

​ 否则 dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1])。

最大子矩阵

​ 首先遍历len=1~n,再将i从1遍历，确定j的值，得出一个len行n列的值，每一列对应相加，得到1行n列的序列，再求线性最大子段和。

​ 得到的最大值就是Len行（从i到j）的最大子矩阵的值。

​ 每次求都不断更新ans = max(ans, dp[i])。

最大正方形

​ 给出一个01矩阵，求都是1的最大正方形的边长

​ dp[i] [j] 表示以x=i,y=j为右下角的最大正方形。 若a[i - 1] [j]、a[i] [j - 1]、a[i - 1] [ j - 1]均为1，则正方形的边长可以加一，即dp[i] [j] + 1。

​ 否则，dp[i] [j] = min(dp[i - 1] [j]、dp[i] [j - 1]、dp[i - 1] [ j - 1])

题目：最大子矩阵

代码：AC代码

最大子段和

线性

​ 定义dp[]一维数组，dp[i]表示以i结尾的最大字段和的值。

​ 有两种情况：

​ 1.独自成串：dp[i] = a[i];

​ 2.与前一个元素连成串：dp[i] = dp[i - 1] + a[i];

​ 合并得：dp[i] = max(dp[i - 1] + a[i], a[i])。

​ 答案是dp[1~n]中最大值。

环形

​ 依照上述方法，求出序列和、最大字段和、最小字段和。

​ 答案 = max(和 - 最小字段和， 最大字段和)。

子集和问题

​ 定义dp[] []bool类二维数组，dp[i] [j] 表示前i个数存在一个子集和等于j，答案就是dp[n] [M]。

​ s[]数组记录集合中元素。

​ 若s[i] > j,则不能放入， dp[i] [j] = dp[i - 1] [j]。

​ 否则, 放不放皆可，dp[i] [j] = (dp[i - 1] [j] || dp[i - 1] [j - s[i]])。

行走问题

​ 类似于爬楼梯。

​ 给出目标阶梯数和每步最多爬几层。

​ 对于每个dp[i]表示走到第i层的步数总数，每次遍历j=i - k~i - 1,dp[i] += dp[j]。

​ 答案就是dp[n]。