线性DP基本知识线性DP就是 按一条直线顺序递推 的动态规划。简单来说我们把问题拆成1、2、3...n依次排列的子问题后面的答案只由前面已经算好的答案推导得出严格遵循从左到右、从前到后的线性顺序有三个核心特征线性阶段子问题严格按一维顺序排列阶段清晰、有序无乱无后效性当前状态只依赖前置状态过去的结果固定不受未来操作影响最优子结构全局最优解一定包含各个子问题的最优解线性DP万能解题四步模板Step1状态定义定义dp[i]的含义dp[i]表示处理前i个元素 / 到第i个位置的最优解最大值/最小值/方案数。部分二维线性DP可定义dp[i][j]依旧遵循线性递推逻辑。Step2状态转移方程推导当前状态与前置状态的关系通用形式dp[i] F(dp[i-1], dp[i-2]...)根据题目决策选/不选、走左/走右、取最大/最小推导对应的递推公式。Step3初始化设置初始边界值一般是dp[0]、dp[1]防止递推过程出现逻辑错误、空值、越界问题。Step4递推顺序严格从左到右遍历i从 2 到 n 依次计算保证求解当前状态时所有前置状态已经计算完成。题目练习B3637 最长上升子序列 - 洛谷朴素写法1.状态定义dp[i]以数组第i个元素结尾的最长上升子序列长度。默认初始化每个元素自身单独构成子序列所以dp[i] 1。状态转移原理想要让a[i]接在前面的元素后面形成更长的上升子序列遍历所有j i前面所有元素如果a[j] a[i]满足上升说明可以把a[i]接在以j结尾的子序列后面。转移方程dp[i] max(dp[i], dp[j] 1)3.初始化所有的数自己可以组成一个子序列所以所有的dp数组初始全都是1#includebits/stdc.h using namespace std; int main(){ int n; cinn; int a[n3]; int dp[n3]; for(int i0;in;i){ cina[i]; dp[i]1; } for(int i0;in;i){ for(int j0;ji;j){ if(a[j]a[i]){ dp[i]max(dp[j]1,dp[i]); } } } int ans1; for(int i0;in;i){ if(dp[i]ans){ ansdp[i]; } } coutans; }二分优化朴素 DP (O(n2))两层循环n 到 (104) 就会 TLE。 贪心 二分把内层 (O(n)) 查找替换成二分 (O(log k))总复杂度 (O(nlog n))可以处理 (n105)。注意该算法直接求出最长上升子序列的长度tails 数组本身不一定是真实子序列。定义tails[i]长度为i1 的严格上升子序列所能得到的最小末尾元素。关键贪心思想 同样长度的上升子序列末尾数字越小越好。末尾越小后面新来的数字越容易接在它后面更容易生成更长子序列。举例同样是长度为 3 的子序列[1,2,3]末尾 3就比[1,2,4]末尾 4更优。初始状态tails为空。遍历每一个元素xa [i]两套分支逻辑1、如果x tails.back()x 比 tails 中所有末尾都大可以接在当前最长子序列后面。push_back(x)tails 数组长度 1代表找到了更长的子序列。2、如果x ≤ tails.back()不能直接延长最长序列。在 tails 数组本身是严格递增里二分查找第一个 ≥ x 的位置lower_bound。将该位置的值替换成 x。替换不改变 tails 长度只更新「该长度子序列的最小末尾」为后面元素做准备。tails 数组永远保持严格递增所以可以二分。严格上升a [j] a [i]lower_bound找第一个 ≥ x允许相等非严格 a [j] ≤ a [i]upper_bound找第一个 x为什么tails.size()就是答案每一次push_back代表我们成功构造出更长一档长度的上升子序列。替换操作只优化末尾不会创造更长子序列。tails 数组的元素个数 我们能实现的最大子序列长度。重要tails[k]代表一定存在原数组中某条长度 k1 的子序列末尾等于 tails [k] 但是把 tails 全部元素连起来不一定是原数组真实出现的子序列。#includebits/stdc.h using namespace std; const int N1e53; int a[N]; int tails[N]; int main(){ int n; cinn; for(int i0;in;i){ cina[i]; } tails[0]a[0]; int len1; for(int i1;in;i){ if(a[i]tails[len-1]){ tails[len]a[i]; len; } else{ int tlower_bound(tails,tailslen,a[i])-tails; tails[t]a[i]; } } coutlen; return 0; }最长连续上升子序列dp[i]以a [i]结尾的「最长连续上升子数组」的长度。初始条件 每个元素自己单独作为一段长度最少是 1所以全部dp[i]1。状态转移逻辑if(a[i-1] a[i]){ dp[i] max(dp[i‑1]1, dp[i]); }如果前一个数字a [i‑1] 当前数字a [i]连续上升可以接在前面一段后面。以 i 结尾的连续长度 以 i‑1 结尾的长度 1。如果不满足a[i‑1]a[i]不能接上dp[i]保持等于 1代表重新开始一段。ans全程记录 dp 数组最大值就是答案。#includebits/stdc.h using namespace std; int main(){ int n; cinn; int a[n3]; int dp[n3]; for(int i0;in;i){ cina[i]; dp[i]1; } int ans1; for(int i1;in;i){ if(a[i-1]a[i]){ dp[i]max(dp[i-1]1,dp[i]); } ansmax(ans,dp[i]); } coutans; }[P1091NOIP 2004 提高组] 合唱队形 - 洛谷合唱队形序列先严格上升到山顶点i之后严格下降。 求最少删除多少人使得剩下队伍满足合唱队形。最少删除人数 总人数 n − 满足条件的最长合唱子序列长度。DP 状态定义1.up[i]以i位置作为结尾的最长上升子序列长度,初始up[i]1每个元素自己构成长度 1 的子序列。 转移u p [ i ] m a x ( u p [ i ] , u p [ j ] 1 ) up[i]max(up[i],up[j]1)up[i]max(up[i],up[j]1)2.down[i]以i位置作为开头的最长下降子序列长度从后往前 DP。d o w n [ i ] m a x ( d o w n [ i ] , d o w n [ j ] 1 ) down[i]max(down[i],down[j]1)down[i]max(down[i],down[j]1)把i当作峰顶 左边上升到i右边从i开始下降i被up、down各算一次所以up[i]down[i]-1就是以i为山顶的完整合唱序列最大长度。 遍历所有i求出全局最大长度maxx。 答案ans n‑maxx。#includebits/stdc.h using namespace std; int up[103],down[103]; int a[103]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; up[i]1; down[i]1; } for(int i1;in;i){ for(int j1;ji;j){ if(a[i]a[j]){ up[i]max(up[i],up[j]1); } } } for(int in;i1;i--){ for(int jn;ji;j--){ if(a[i]a[j]){ down[i]max(down[i],down[j]1); } } } int maxx-1; for(int i1;in;i){ maxxmax(maxx,up[i]down[i]-1); } int ansn-maxx; coutans; return 0; }91. 解码方法 - 力扣LeetCode题目数字字符串1~26映射 A‑Z求一共有多少种解码方案。例如12可以解码成AB、L答案为 2。DP 状态定义dp[i]字符串前 i 个字符的解码总方案数。dp[0] 1空串虚拟边界代表 “什么都不选1 种方案”方便做加法。dp[n]就是答案整个字符串前 n 位全部解码的方案。两种转移来源单独拿最后 1 位解码如果当前字符s[i‑1]不是0可以单独作为一个编码。 前面前i‑1位有dp[i‑1]种方案直接继承dp[i] dp[i‑1]拿末尾两个字符合并解码需要满足 3 个条件 1至少有两位字符i12第一位不能是 0不能出现06这种s[i‑2]!03组成的数字 ≤26 满足条件则末尾两位看成整体前面前i‑2位所有方案都可以接上来dp[i] dp[i‑2]最终dp[i] 情况1的方案数 情况2的方案数class Solution { public: int numDecodings(string s) { int ns.size(); int dp[n2]; for(int i1;in;i){ dp[i]0; } dp[0]1; for(int i1;in;i){ if(s[i-1]!0){ dp[i]dp[i-1]; } if(i1s[i-2]!0(s[i-2]-0)*10s[i-1]-026){ dp[i]dp[i-2]; } } return dp[n]; } };639. 解码方法 II - 力扣LeetCode状态dp[i]表示字符串前i个字符解码方案数dp[0]1虚拟空串边界。线性 DPi从 1 到l顺序遍历dp [i]只依赖dp [i‑1]、dp [i‑2]前面的状态无后效性。转移来源两种两种取其和当前字符单独解码根据是否是*乘对应系数加到dp [i‑1]末尾两个字符合并解码分 4 种字符组合统计合法组合数量乘以dp[i‑2]累加到答案。class Solution { public: int numDecodings(string s) { int ls.size(); const int N1e53; vectorlong longdp(l1,0); dp[0]1; const int mod1e97; if(s[0]0){ return 0; } for(int i1;il;i){ if(s[i-1]!0){ if(s[i-1]*){ dp[i]9*dp[i-1]%mod; dp[i]%mod; } else{ dp[i]dp[i-1]%mod; dp[i]%mod; } } if(i1s[i-2]!0){ if(s[i-1]*s[i-2]*){ dp[i]dp[i-2]*15%mod; dp[i]%mod; } else if(s[i-2]*){ if(s[i-1]-06s[i-1]-00){ dp[i]2*dp[i-2]%mod; dp[i]%mod; } else{ dp[i]dp[i-2]%mod; dp[i]%mod; } } else if(s[i-1]*){ if(s[i-2]-01){ dp[i]dp[i-2]*9%mod; dp[i]%mod; } else if(s[i-2]-02){ dp[i]dp[i-2]*6%mod; dp[i]%mod; } else{ dp[i]0; } } else{ if((s[i-2]-0)*10s[i-1]-026){ dp[i]dp[i-2]%mod; dp[i]%mod; } } } } return dp[l]; } };