经典树型DP状态压缩DP入门

Leetcode常见DP题状态转移方程一、概述动态规划（Dynamic Programming, DP）是算法设计中的一种常用方法，它通常用于优化递归算法，解决重叠子问题。

Leetcode上有许多经典动态规划问题，而理解状态转移方程是解决这些问题的关键。

本文旨在总结Leetcode常见DP题的状态转移方程，帮助读者更好地理解和掌握动态规划算法的应用。

二、背包问题1. 0-1背包问题问题描述：给定一组物品，每种物品都有重量和价值，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]), 1 <= i <= n, 1 <= j <= C```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，C 表示背包的容量，n为物品的个数。

2. 完全背包问题问题描述：给定一组物品，每种物品都有重量和价值，每种物品不限数量，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i]), 1 <= i <= n, 1 <= j <= C```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，C 表示背包的容量，n为物品的个数。

3. 多重背包问题问题描述：给定一组物品，每种物品都有重量和价值，每种物品有限数量，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*weight[i]] + k*value[i]), 1 <= i <= n, 1 <= j <= C, 0 <= k <= num[i]```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，num[i]表示第i个物品的数量，C表示背包的容量，n为物品的个数。

DP⼊门（2）——DAG上的动态规划有向⽆环图（DAG,Directed Acyclic Graph）上的动态规划是学习动态规划的基础。

很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。

⼀、DAG模型【嵌套矩形问题】问题：有n个矩形，每个矩形可以⽤两个整数a、b描述，表⽰它的长和宽。

矩形X(a , b)可以嵌套在矩形Y(c , d)中当且仅当a<c,b<d,或者b<c,a<d(相当于把矩形X旋转90°)。

例如(1,5)可以嵌套在(6, 2)内，但不能嵌套在(3, 4)内。

你的任务是选出尽可能多的矩形排成⼀⾏，使得除了最后⼀个之外，每个矩形都可以嵌套在下⼀个矩形内。

如果有多解，矩形编号的字典序应尽量⼩。

分析：矩形之间的“可嵌套”关系是⼀个典型的⼆元关系（我的理解是两个矩形之间存在关系），⼆元关系可以⽤图来建模。

如果矩形X可以嵌套在矩形Y⾥，就从X到Y连⼀条有向边。

这个有向图必然是⽆环的，因为⼀个矩形⽆法直接或间接地嵌套在⾃⼰内部。

换句话说，它是⼀个DAG。

这样，所要求的便是DAG上的最长路径。

【硬币问题】问题：有n种硬币，⾯值分别为V1, V2, ..., V n，每种都有⽆限多。

给定⾮负整数S，可以选⽤多少个硬币，使得⾯值之和恰好为S？输出硬币数⽬的最⼩值和最⼤值。

1 <= n <= 100, 0 <= S <= 10000, 1 <= V i <= S。

分析：此问题尽管看上去和嵌套矩形问题很不⼀样，但本题的本质也是DAG上的路径问题。

将每种⾯值看作⼀个点，表⽰“还需要凑⾜的⾯值”，则初始状态为S，⽬标状态为0。

若当前在状态 i，每使⽤⼀个硬币 j，状态便转移到i - V j。

补充：这个模型和上⼀题类似，但也有⼀些明显地不同之处：上题并没有确定路径的起点和终点（可以把任意矩形放在第⼀个和最后⼀个），⽽本题的起点必须为S，终点必须为0。

P1433吃奶酪（洛⾕）状压dp解法嗯？这题竟然是个绿题。

这个题真的不（很）难，我们只是不会计算2点之间的距离，他还给出了公式，这个就有点……我们直接套公式去求出需要的值，然后普通的状压dp就可以了。

是的状压dp。

这个题的数据加强了，早已经不是搜索可以驾驭的了。

搜索的效率实在是有点低，我来算⼀个不准的效率，搜索的效率应该是O(n!)。

应该是吧。

状压dp只需要短短的O(2^n*n*n就可以了)。

状态共有2^n*n个，每次查找下⼀步需要O(n)的效率，所以状压dp的效率是O(2^n*n*n)。

状压dp⽤⼀个⼆进制数表⽰哪个奶酪曾经吃过，我们先看看这些⼆进制数的基本操作：不知道与，或，异或运算的可以百度⼀下。

第⼀种操作，查询第i个奶酪有没有吃过。

x表⽰现在奶酪的情况（2进制数）我们要判断第i个奶酪有没有被吃if((x&(1<<i-1))==0)这样写就可以啦。

其中&的意思是按位与运算，就是说在2进制下，2位同时为1，结果才为1，也就是说，如果第i个奶酪被吃掉了，x那⼀位就是1，按位与运算后的结果也是1，如果按位与运算后的结果是0，第i个奶酪就没有被吃掉。

第⼆种操作，吃掉第i个奶酪后，x会变成什么样⼦？x=x|(1<<i-1)这样写，|是按位或运算，就是在⼆进制⾥，2位有⼀个为1，结果为1，1<<i-1的第i位是1，和x进⾏按位或运算就让x的第i位也变成1了。

做这个题只需要这两个操作，剩下的操作有兴趣的同学可以去百度⼀下。

接下来就是代码了：#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdio>using namespace std;double a[20],b[20],shu=999999.0;//初始化double dp[40000][20];double sz[20][20];//sz[i][j]是表⽰第i个奶酪到第j个奶酪有多远。

DP及其操作流程DP（动态规划）是一种通过空间换时间的优化方法，适用于有重叠子问题和最优子结构性质的问题。

DP算法适用于求解最优化问题，其基本思想是将原问题划分为若干个相互重叠的子问题，逐步求解子问题，并保存每个子问题的最优解，最终得到原问题的最优解。

DP的操作流程包括以下几个步骤：1.确定状态：首先确定问题的状态，即用什么变量来表示问题的状态。

状态可以是用一个或多个变量来描述问题的特征，例如背包问题中的背包容量和物品数量。

2.定义状态转移方程：根据问题的最优子结构性质，定义状态之间的转移关系。

状态转移方程描述了子问题之间的递推关系，可以通过递归或迭代的方式求解。

3.初始化边界条件：确定初始状态的值，即将问题的边界条件定义为初始状态的值。

通常需要设置初始状态或者一些特殊的边界条件，以便开始DP算法的递推过程。

4.递推求解：根据状态转移方程和初始状态，逐步求解子问题，并保存每个子问题的最优解。

通常需要使用一个二维数组或者其他数据结构来保存子问题的解。

5.返回结果：根据子问题的最优解，得到原问题的最优解。

通常是在递推过程中保存一些状态信息，最后根据这些信息恢复原问题的最优解。

DP算法的时间复杂度通常是O(n^2)或者O(n^3)，其中n是问题的规模。

通过合适地定义状态转移方程和设计递推过程，可以优化DP算法的时间复杂度，降低计算复杂度。

举个例子来说明DP算法的操作流程：假设有一个背包容量为W，有n 个物品，每个物品的重量分别为w1，w2，...，wn，价值分别为v1，v2，...，vn。

要求在背包容量不超过W的情况下，装入物品的最大总价值。

1.确定状态：定义状态dp[i][j]表示在前i个物品中，背包容量为j 时的最大总价值。

2.定状态转移方程：dp[i][j]的值可以由dp[i-1][j]和dp[i-1][j-w[i]]+v[i]决定，即在前i-1个物品的情况下，背包容量为j的最大总价值与装入第i个物品后的最大总价值之间取最大值。

树的直径的两种求法打多校才发现连树的直径都忘了，赶紧来复习⼀下树的直径这⾥只讲裸的树的直径..有两种常见的⽅法去求树的直径树形dp写法：第⼀种是树形dp，我们随便选个结点作为根将有根树转化为⽆根树，⽤dp[x]表⽰以x为根的⼦树中从x出发的最长链的长度，如果Yi是x的⼉⼦们，那么状态转移是这样的dp[x]=max(dp[x],dp[y]+Edge)，接下来考虑经过x的最长链的长度f[x]，那么max(f[i]，1<=i<=n)就是树的直径了，假设yi,yj是x的两个直接相连的结点，那么f(x)=max(dp[yi]+dp[yj]+x与yi,yj的距离）具体实现就在下⾯了#include <bits/stdc++.h>using namespace std;#define de(a) cout << #a << " = " << a << endl#define rep(i, a, n) for (int i = a; i < n; i++)#define per(i, a, n) for (int i = n - 1; i >= a; i--)typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> PII;typedef pair<double, double> PDD;typedef vector<int, int> VII;#define inf 0x3f3f3f3fconst ll INF = 0x3f3f3f3f3f3f3f3f;const ll MAXN = 1e3 + 7;const ll MAXM = 1e5 + 7;const ll MOD = 1e9 + 7;const double eps = 1e-6;const double pi = acos(-1.0);int n, m;struct Edge{int from, to, val;int next;} E[MAXM];int cnt = -1;int ans = -inf;int head[MAXN];int dp[MAXN]; /* dp[x]表⽰从结点x出发，往以x作为根的⼦树⾛，能够到达的最远距离 */void add(int from, int to, int val){E[++cnt].from = from;E[cnt].to = to;E[cnt].val = val;E[cnt].next = head[from];head[from] = cnt;}void init(){ans = -inf;cnt = -1;memset(head, -1, sizeof(head));memset(dp, 0, sizeof(dp));}/* 求树的直径 */void tree_dp(int u, int fa) /* 随便选个结点作为根结点把树转换成有根树 */{for (int i = head[u]; i != -1; i = E[i].next){int to = E[i].to;if (fa == to)continue;tree_dp(to, u);ans = max(ans, dp[u] + dp[to] + E[i].val);dp[u] = max(dp[u], dp[to] + E[i].val);}}int main(){init();cin >> n >> m;for (int i = 0; i < m; i++){int u, v, val;cin >> u >> v >> val;add(u, v, val); //建边add(v, u, val);}tree_dp(1, -1);cout << ans << endl;return 0;}两次dfs或者bfs：这样写还⽅便计算出直径上的具体结点。

信息学奥赛——树型动态规划的实例分析树型动态规划（Tree Dynamic Programming）是信息学奥赛中常用的一种算法思想，在解决一些与树相关的问题时非常有效。

本文将通过一个具体的实例对树型动态规划进行详细分析。

假设有一棵有根树，每个节点上都有一个非负整数权值，并且每个节点下都可能有若干个子节点。

现在要求选择一些节点，使得选中的节点的权值之和尽可能大，但是不能选择相邻的节点。

我们需要设计一个算法来解决这个问题。

首先，我们可以观察到如果一个节点被选中，那么它的子节点就不能被选中。

于是，我们可以定义一个动态规划的状态dp[i]表示以节点i为根的子树中选择节点的最大权值之和。

对于根节点，我们有两种情况：1. 根节点i被选择，那么它的子节点就不能被选择。

所以dp[i] = sum(dp[j])，其中j表示i的所有子节点。

2. 根节点i不被选择，那么它的所有子节点都可以被选择。

所以dp[i] = sum(max(dp[j], dp[k]))，其中j和k分别表示i的所有孩子节点的子节点。

通过对根节点的两种状态的分析，我们可以得到一个递推关系：dp[i] = max(sum(dp[j]), sum(max(dp[k], dp[l])))，其中j表示i的所有子节点，k和l分别表示i的所有孩子节点的子节点。

接下来，我们需要设计一个合适的递归算法来计算dp[i]。

我们可以使用深度优先（DFS）的方式来处理每个节点，实现递归的过程。

具体的伪代码如下：```DFS(i):visit[i] = truefor j in i的所有子节点：if visit[j] == false:DFS(j)dp[i] += dp[j]for k in i的所有孩子节点：for l in k的所有子节点：dp[i] += max(dp[k], dp[l])```最后，我们只需要调用DFS函数以根节点为参数，可以得到整棵树的最优解。

dp状态转移方程
DP（动态规划）状态转移方程是一种常用的算法思想，可以用来解决很多实际问题。

在DP算法中，状态转移方程是至关重要的一部分，它用来描述如何从一个状态转移到另一个状态。

DP状态转移方程通常可以用以下公式表示：
dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k])
其中，dp[i] 表示状态 i 的最优解，f 表示状态转移方程，k 表示转移的步长。

在实际问题中，状态转移方程的形式和具体实现方法都有很大的差别，需要根据具体问题进行调整和优化。

但是，通常状态转移方程都具有以下特点：
1. 最优子结构性质
即问题的最优解包含子问题的最优解。

这个特点是DP算法的核心，也是状态转移方程的基础。

2. 无后效性
即某个状态一旦确定，就不受之后决策的影响。

这个特点是DP 算法的前提条件，也是状态转移方程的基础。

3. 重叠子问题性质
即子问题之间存在重叠。

这个特点是DP算法的优势，可以通过记忆化搜索等方法进行优化。

总之，DP状态转移方程是一种非常重要的算法思想，在实际问题中发挥着巨大的作用。

熟练掌握状态转移方程的原理和应用方法，
对于提高算法竞赛和面试的能力都非常有帮助。

Codeforces1179D树形DP斜率优化题意：给你⼀颗树，你可以在树上添加⼀条边，问添加⼀条边之后的简单路径最多有多少条？简单路径是指路径中的点只没有重复。

思路：添加⼀条边之后，树变成了基环树。

容易发现，以基环上的点为根的⼦树的点中的简单路径没有增加。

所以，问题相当于转化为找⼀个基环，使得以基环上的点为根的⼦树Σ(i从1到n) sz[i] * (sz[i] - 1) / 2最⼩。

我们把式⼦转化⼀下变成求(sz[i]的平⽅和 - n) / 2。

相当于我们需要求sz[i]的平⽅和。

但是，我们并不知道哪个是基环，怎么求sz呢？我们发现⼀个性质：添加的边连接的两点⼀定是树中度数为1的点，否则，我们⼀定可以缩⼩平⽅和。

所以，根据这个性质，我们可以进⾏树形dp。

设dp[i]为以i为根的⼦树中，选择从i到⼦树中的某个叶⼦节点的路径为基环上的点，可以获得的最⼩的平⽅和。

dp[i] = min(dp[son] + (sz[i] - sz[son]) ^ 2)。

我们假设选择的基环是u -> lca(u, v) -> v ,假设fu为u到lca(u, v)的路径中lca(u, v)的前⾯⼀个节点，fv同理，那么平⽅和为ans = dp[fu] + dp[fv] + (n - sz[fu] - sz[fv]) ^ 2。

所以，我们在深搜的时候，找到所有孩⼦的dp值和sz，枚举是哪两个孩⼦来更新平⽅和，这样最坏情况是O(n ^ 2)的，会超时。

发现状态转移⽅程中有fu和fv的乘积项，我们可以考虑斜率优化。

把⽅程移项: dp[fv] = 2 * (n - sz[fu]) * sz[fv] + (ans - dp[fu] - 2 * n * sz[fu])。

那么相当于是以sz[fv]为横坐标，dp[fv]为纵坐标，斜率为2 * (n - sz[fu])的直线，要ans最⼩，需要截距最⼩。

我们把sz从⼩到⼤排序，⽤单调队列维护⼀个下凸包，之后在单调队列⾥⼆分即可。

1. 资源问题1-----机器分配问题f[i,j]:=max(f[i-1,k]+w[i,j-k]);2. 资源问题2------01背包问题f[i,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3. 线性动态规划1-----朴素最长非降子序列f[i]:=max{f[j]+1}4. 剖分问题1-----石子合并f[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5. 剖分问题2-----多边形剖分f[i,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);6. 剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7. 资源问题3-----系统可靠性(完全背包)f[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]};8. 贪心的动态规划1-----快餐问题f[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3};9. 贪心的动态规划2-----过河f[i]=min{{f(i-k)} (not stone[i]){f(i-k)}+1} (stone[i]); +贪心压缩状态10. 剖分问题4-----多边形-讨论的动态规划F[i,j]:=max{正正f[I,k]*f[k+1,j];负负g[I,k]*f[k+1,j];正负g[I,k]*f[k+1,j];负正f[I,k]*g[k+1,j];} g为min11. 树型动态规划1-----加分二叉树(从两侧到根结点模型)F[i,j]:=max{f[i,k-1]*f[k+1,j]+c[k]};12. 树型动态规划2-----选课(多叉树转二叉树,自顶向下模型)f[i,j]表示以i为根节点选j门功课得到的最大学分f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]};13. 计数问题1-----砝码称重f[f[0]+1]=f[j]+k*w[j];(1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];)14. 递推天地1------核电站问题f[-1]:=1; f[0]:=1;f[i]:=2*f[i-1]-f[i-1-m];15. 递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];16. 最大子矩阵1-----一最大01子矩阵f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;ans:=maxvalue(f);17. 判定性问题1-----能否被4整除g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)18. 判定性问题2-----能否被k整除f[i,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n20. 线型动态规划2-----方块消除游戏f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), //dof[i,p,k+len[j]]+f[p+1,j-1,0] //not do}; ans:=f[1,m,0];21. 线型动态规划3-----最长公共子串，LCS问题f[i,j]=0 (i=0)&(j=0);f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);22. 最大子矩阵2-----最大带权01子矩阵O(n^2*m)枚举行的起始，压缩进数列，求最大字段和，遇0则清零23. 资源问题4-----装箱问题(判定性01背包)f[j]:=(f[j] or f[j-v[i]]);24. 数字三角形1-----朴素の数字三角形f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);25. 数字三角形2-----晴天小猪历险记之Hill同一阶段上暴力动态规划f[i,j]:=min(f[i,j-1],f[i,j+1],f[i-1,j],f[i-1,j-1])+a[i,j];26. 双向动态规划1数字三角形3-----小胖办证f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]);27. 数字三角形4-----过河卒//边界初始化f[i,j]:=f[i-1,j]+f[i,j-1];28. 数字三角形5-----朴素的打砖块f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);29. 数字三角形6-----优化的打砖块f[i,j,k]:=max{g[i-1,j-k,k-1]+sum[i,k]};30. 线性动态规划3-----打鼹鼠’f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]);31. 树形动态规划3-----贪吃的九头龙f[i,j,k]:=min(f[x1,j1,1]+f[x2,j-j1-1,k]+d[k,1]*cost[i,fa[i]]] {Small Head}, f[x1,j1,0]+f[x2,j-j1,k]+d[k,0]*cost[i,fa[i]] {Big Head});f[0,0,k]:=0; f[0,j,k]:=max(j>0)d[i,j]:=1 if (i=1) and (j=1)1 if (i=0) and (j=0) and (M=2)0 else32. 状态压缩动态规划1-----炮兵阵地Max(f[Q*(r+1)+k],g[j]+num[k]);If (map[i] and plan[k]=0) and((plan[P] or plan[q]) and plan[k]=0);33. 递推天地3-----情书抄写员f[i]:=f[i-1]+k*f[i-2];34. 递推天地4-----错位排列f[i]:=(i-1)(f[i-2]+f[i-1]);f[n]:=n*f[n-1]+(-1)^(n-2);35. 递推天地5-----直线分平面最大区域数f[n]:=f[n-1]+n:=n*(n+1) div 2 + 1;36. 递推天地6-----折线分平面最大区域数f[n]:=(n-1)(2*n-1)+2*n;37. 递推天地7-----封闭曲线分平面最大区域数f[n]:=f[n-1]+2*(n-1);:=sqr(n)-n+2;38 递推天地8-----凸多边形分三角形方法数f[n]:=C(2*n-2,n-1) div n;对于k边形f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)39 递推天地9-----Catalan数列一般形式1,1,2,5,14,42,132f[n]:=C(2k,k) div (k+1);40 递推天地10-----彩灯布置排列组合中的环形染色问题f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);41 线性动态规划4-----找数线性扫描sum:=f[i]+g[j];(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)42 线性动态规划5-----隐形的翅膀min:=min{abs(w[i]/w[j]-gold)};if w[i]/w[j]<gold then inc(i) else inc(j);43 剖分问题5-----最大奖励f[i]:=max(f[i],f[j]+(sum[j]-sum[i])*i-t;44 最短路1-----Floydf[i,j]:=max(f[i,j],f[i,k]+f[k,j]);ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];45 剖分问题6-----小H的小屋F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);46 计数问题2-----陨石的秘密（排列组合中的计数问题）Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);47 线性动态规划------合唱队形两次F[i]:=max{f[j]+1}＋枚举中央结点48 资源问题------明明的预算方案：加花的动态规划f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]]);49 资源问题-----化工场装箱员50 树形动态规划-----聚会的快乐f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t[i]^.son,0]);f[i,0]:=sigma(f[t[i]^.son,3]);51 树形动态规划-----皇宫看守f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t[i]^.son,0]);f[i,0]:=sigma(f[t[i]^.son,2]);52 递推天地-----盒子与球f[i,1]:=1;f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);53 双重动态规划-----有限的基因序列f[i]:=min{f[j]+1}g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j]);54 最大子矩阵问题-----居住空间f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),min(f[i,j,k-1],f[i-1,j-1,k])),min(min(f[i-1,j,k-1],f[i,j-1,k-1] ),f[i-1,j-1,k-1]))+1;55 线性动态规划------日程安排f[i]:=max{f[j]}+P[I]; (e[j]<s[i])56 递推天地------组合数C[i,j]:=C[i-1,j]+C[i-1,j-1];C[i,0]:=157 树形动态规划-----有向树k中值问题F[I,r,k]:=max{max{f[l[i],I,j]+f[r[i],I,k-j-1]},f[f[l[i],r,j]+f[r[i],r,k-j]+w[I,r]]};58 树形动态规划-----CTSC 2001选课F[I,j]:=w[i](if i∈P)+f[l[i],k]+f[r[i],m-k](0≤k≤m)(if l[i]<>0);59 线性动态规划-----多重历史f[i,j]:=sigma{f[i-k,j-1]}(if checked);60 背包问题(+-1背包问题+回溯)-----CEOI1998 Substractf[i,j]:=f[i-1,j-a[i]] or f[i-1,j+a[i]];61 线性动态规划(字符串)-----NOI 2000 古城之谜f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1};f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]};62 线性动态规划-----最少单词个数f[i,j]:=max{f[i,j],f[u-1,j-1]+l};63 线型动态规划-----APIO2007 数据备份状态压缩＋剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划f[i]:=min(g[i-2]+s[i],f[i-1]);64 树形动态规划-----APIO2007 风铃f[i]:=f[l]+f[r]+{1 (if c[l]<c[r])};g[i]:=1(d[l]<>d[r]) 0(d[l]=d[r]);g[l]=g[r]=1 then Halt;65 地图动态规划-----NOI 2005 adv19910F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];66 地图动态规划-----优化的NOI 2005 adv19910F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;67 目标动态规划-----CEOI98 subtraF[I,j]:=f[I-1,j+a[i]] or f[i-1,j-a[i]];68 目标动态规划----- Vijos 1037搭建双塔问题F[value,delta]:=g[value+a[i],delta+a[i]] or g[value,delta-a[i]];69 树形动态规划-----有线电视网f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j]);leaves[i]>=p>=l, 1<=q<=p;70 地图动态规划-----vijos某题F[i,j]:=min(f[i-1,j-1],f[i,j-1],f[i-1,j]);71 最大子矩阵问题-----最大字段和问题f[i]:=max(f[i-1]+b[i],b[i]); f[1]:=b[1];72 最大子矩阵问题-----最大子立方体问题枚举一组边i的起始，压缩进矩阵B[I,j]+=a[x,I,j];枚举另外一组边的其实，做最大子矩阵73 括号序列-----线型动态规划f[i,j]:=min(f[i,j],f[i+1,j-1] (s[i]s[j]=”()”or(”[]”)),f[i+1,j+1]+1 (s[j]=”(”or”[” ) , f[i,j-1]+1(s[j]=”)”or”]”);74 棋盘切割-----线型动态规划f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]};75 概率动态规划-----聪聪和可可(NOI2005)x:=p[p[i,j],j];f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1;f[I,i]=0;f[x,j]=1;76 概率动态规划-----血缘关系F[A, B]=(f[A0, B]+P[A1, B])/2;f[i,i]=1;f[i,j]=0;(i,j无相同基因)77 线性动态规划-----决斗F[i,j]=(f[i,j] and f[k,j]) and (e[i,k] or e[j,k]); (i<k<j)78 线性动态规划-----舞蹈家F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]]);79 线性动态规划-----积木游戏F[i,a,b,k]=max(f[a+1,b,k],f[i+1,a+1,a+1,k],f[i,a+1,a+1,k]);80 树形动态规划（双次记录）-----NOI2003 逃学的小孩朴素的话枚举节点i和离其最远的两个节点j,k O(n^2)每个节点记录最大的两个值，并记录这最大值分别是从哪个相邻节点传过来的。

浅谈线段树优化DP
浅谈线段树优化DP
本篇随笔浅谈⼀下线段树优化DP。

⼀、关于DP优化的两种⽅式
DP算法是⼤家⽿熟能详的最优化算法之⼀。

有的时候，我们设计DP的时候，需要采取措施进⾏DP优化来适应题⽬对时间空间的要求。

⼀般来讲，DP的优化有两种⽅式：第⼀种是针对状态设计进⾏优化。

⽐如滚动数组优化⼀维。

⽐如0/1背包优化枚举，⽐如状压和倍增DP等等。

第⼆种是针对转移过程进⾏优化，⽐如⼀次转移是\(O(n)\)的，卡时间，就想办法通过⼀些办法把⼀次转移的时间复杂度降低。

⽐如，对于⼀些数列问题，可以通过递推公式进⾏通项公式的计算，进⽽做到\(O(n)\rightarrow O(1)\)的转移。

还⽐如说，⽤⼀些数据结构维护转移所需的⼀些信息，以达到优化转移的效果。

⼆、线段树优化DP的概念
在DP过程中架线段树对DP的转移进⾏优化，就被叫做线段树优化DP。

三、例题体会
多讲没⽤，上题。

⽐如这道：
这道题是很经典的线段树优化DP。

设计状态什么的都是次要的。

转移的时候，不加优化是⼀次\(O(n)\)，优化后变成⼀次\(O(\log n)\)，总复杂度变成：\(O(n\log n)\)。

通过这道题，我们总结⼀下线段树优化DP的⼀半步骤。

⼀、弄清楚线段树维护的是什么信息。

⼆、弄清楚线段树维护的信息在转移过程中是否有修改，怎么修改。

三、弄清楚线段树维护的信息在转移过程中是否随状态的更新⽽改变。

⼤约就是这样。

1.为什么要用动态规划?众所周知，大多数题目都能用深搜或广搜解决，那为什么还要用动态规划呢？其原因就是在深搜或广搜中，大量状态都被重复运算，浪费了大量时间。

而动态规划与深搜和广搜一个最大的不同就是动态规划在完成该状态的运算后将该状态的值记下来，以便以后使用，从而大大减少了运算量，提高程序在规定时间内解题能力。

因为在分区联赛中对时间复杂度要求比较严格（大多数题都要求1s出解）而对空间复杂度要求不是十分严格（规定64m内存，而一般需要的内存不超过20m）。

所以，对于一个解决分区联赛的程序来说，应适当地牺牲空间而追求时间，动态规划这一类算法很好地符合了这一点。

所以对于大多数分区联赛题目，动态规划就是最好的，最能抓分的算法。

2.拿到一个题目，如何判断出他是动态规划类题目？动态规划类题目有两个显著特点：具有最优子结构和后效性。

对于最优子结构，由于动态规划类问题都是需要求极值，倘若不具有最优子结构，则无法求出所需的最值。

对于无后效性，简单一点说就是当你处理完第i个状态，处理第i+1个状态时，就是天塌下来，第i个状态的值都不会改变了，要是在处理后面的状态时还要对前面的状态的值进行修改，就不是动态规划，而是搜索了。

当符合了这两个特点时，你应该就能用动态规划方法做题了。

但是如果状态过多，在有限的内存下无法保存的话，还是要考虑其他方法（如“生日蛋糕”问题）。

3.对于一个动态规划题目，如何去思考它？拿到一个动态规划题目，首先应该想到：它有哪几种状态需要我们保存，以便于在程序后期执行时加利利用，在分区联赛中，尽量把所有状态都列举记录下来，因为如前面所说，分区联赛对于空间复杂度的要求并不是十分严格，不必刻意地去减少状态数而降低空间复杂度，这样的话会增加编程的复杂度和编程的时间，对于你整场考试会有一定不利的影响。

得分才是硬道理吗，程序能过，能得分就行，何必为了那几k内存的优化而久久放不下手呢？不过对于某些状态过多的动态规划题目，某些不必要的状态不必记录，否则就会出现数组清零占用大量时间，甚至超出内存等影响你得分的问题，这些都是不应该的，我们应该尽量避免出现这个问题。

dp的使用流程什么是dpdp（Dynamic Programming，动态规划）是一种解决多阶段决策问题的方法。

它将问题分解成若干个阶段，并通过记录每个阶段的最优解来得到整体的最优解。

dp广泛应用于算法和计算机科学领域，例如图论、优化问题等。

dp的使用流程dp的使用流程一般包括下面几个步骤：1.定义状态：将问题抽象成状态的集合，每个状态代表问题的一个子问题。

2.初始化状态：确定初始状态的值。

3.状态转移方程：定义问题从一个状态转移到另一个状态的演变规则。

4.计算最优解：按照状态转移方程，计算得到最优解。

下面我们将以一个经典的背包问题为例，详细介绍dp的使用流程。

背包问题背包问题是dp中常见的一个问题，题目描述为：给定一个可装载重量为W的背包和N个物品，每个物品有重量wt和价值val，求解如何装载物品才能使得背包中所装物品的总价值最大。

dp的使用流程示例：背包问题1. 定义状态我们定义dp[i][j]表示在前i个物品中，总重量不超过j的情况下可以获得的最大价值。

2. 初始化状态对于dp数组，我们需要注意边界条件。

因此，初始状态为dp[0][j] = 0（其中0 <= j <= W），意义为前0个物品在任意重量下的最大价值都是0。

同理，dp[i][0] = 0（其中0 <= i <= N），意义为任意物品在重量为0下的最大价值都是0。

3. 状态转移方程在背包问题中，我们需要根据物品的重量和价值来决定是否选择装入背包。

我们可以分为两种情况进行分析：•如果第i个物品的重量超过了当前背包的重量j，则第i个物品不能装入背包中，此时，dp[i][j]等于前i-1个物品在重量为j下的最大价值，即dp[i][j] = dp[i-1][j]。

•如果第i个物品的重量不超过背包的重量j，则我们需要判断装入第i 个物品和不装入第i个物品哪种方案可以获得更大的价值。

我们可以选择装入第i个物品，此时dp[i][j]等于前i-1个物品在重量为j-wt[i]下的最大价值加上第i个物品的价值val[i]；或者不装入第i个物品，此时dp[i][j]等于前i-1个物品在重量为j下的最大价值。

noi知识点加*号是选学，加粗为重点，重要值排序不分先后基础贪⼼、枚举、分治、⼆分、倍增、*构造、⾼精、模拟图论图最短路（dijkstra、spfa、floyd），差分约束最⼩⽣成树（kruskal、prim）并查集（扩展域）拓扑排序⼆分图染⾊，*⼆分图匹配tarjan找scc、桥、割点，缩点*分数规划树树上倍增（LCA）树的直径、树的重⼼dfs序*树链剖分数论gcd、lcm埃⽒筛法exgcd，求解同余⽅程、逆元快速幂*组合数学矩阵链表、队列（单调队列）、栈（单调栈）堆、st表、hash表线段树、树状数组字典树*分块动态规划背包DP、树形DP、记忆化搜索、递推区间DP、序列DP*DP优化（不涉及斜率优化、四边形不等式等等）搜索暴搜（dfs、bfs）搜索的剪枝启发式搜索（A*）迭代加深搜索、* IDA**随机化搜索其他算法STL的基本使⽤⽅法脑洞的正确使⽤⽅法*KMP*状态压缩冲省选的，先把整理的NOIP知识点学扎实，注意⼀定要学扎实加粗是重点，星号是选学学⽆⽌境，欢迎⼤家继续补充~图论⽹络流（dinic，SAP，ISAP选⼀个，费⽤流写EK就⾏。

*zkw费⽤流），⼆分图点分治，边分治，*动态点分治树链剖分，动态树，树分块虚树，*prufer编码*仙⼈掌算法带权并查集Splay（作为平衡树和维护区间），Treap，替罪⽺树线段树（权值线段树），树状数组，*线段树合并分块，块状链表，*双向链表凸包树套树主席树，可持久化trie，*其它可持久化数据结构莫队算法，*树上莫队，CDQ分治，整体⼆分⼆维线段树，*KDtree*舞蹈链，*⼆进制分组，*左偏树，*超哥线段树，*后缀平衡树，*fhqTreap字符串相关及数据结构hash（⾃然溢出，双hash）kmp，AC⾃动机，trie后缀数组manacher，最⼩表⽰法*后缀⾃动机，*回⽂⾃动机，*后缀树数学线性筛，积性函数，容斥原理，莫⽐乌斯反演exgcd，费马⼩定理，Lucas定理，⾼中排列组合⾼斯消元，概率与期望相关中国剩余定理，BSGS，欧拉定理矩阵乘法单纯形法解线性规划FFT线性代数（⾏列式）*Simpson积分，⾼中求导与积分*群论*⽣成函数，多项式类算法博弈论相关，*密码学，阶，原根计算⼏何向量的点积/叉积，计算⼏何基础*⼆维计算⼏何相关，*三维计算⼏何相关*半平⾯交，*旋转卡壳，*三⾓剖分搜索A*，记忆化搜索，迭代深搜，双向⼴搜模拟退⽕，爬⼭算法，*随机增量法动态规划基础DP，树形DP，数位DP，状压DP，期望DP，基环树DP，*插头DP斜率优化，矩乘优化，单调队列优化，倍增优化，*四边形不等式优化trie图DP，*仙⼈掌DP其他算法构造，乱搞，随机化，三分法，打表，启发式合并Huffman树，2-sat，*朱刘算法。