网站搭建策划书,cms网站后台模版,重庆建设工程公司网站,电子商务网站开发费用【线性DP】模型总结
最长上升子序列
DP法
dp[i]表示以i结尾的最长上升子序列的长度。
对于每个i#xff0c;遍历j1~i-1,若a[j] a[i], 则dp[i] max(dp[i], dp[j] 1);
二分法
可以优化时间复杂度。
dp[]数组用来存储当前最长上升子序列。
若dp[]数…【线性DP】模型总结
最长上升子序列
DP法
dp[i]表示以i结尾的最长上升子序列的长度。
对于每个i遍历j1~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])。
最大子矩阵
首先遍历len1~n,再将i从1遍历确定j的值得出一个len行n列的值每一列对应相加得到1行n列的序列再求线性最大子段和。
得到的最大值就是Len行从i到j的最大子矩阵的值。
每次求都不断更新ans max(ans, dp[i])。
最大正方形
给出一个01矩阵求都是1的最大正方形的边长
dp[i] [j] 表示以xi,yj为右下角的最大正方形。 若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层的步数总数每次遍历ji - k~i - 1,dp[i] dp[j]。
答案就是dp[n]。
