内容提要：
动态规划
数位DP
树形DP
区间DP
动态规划
斐波那契数列
f(0)=0,f(1)=1,......,f(n)=f(n-1)+f(n-2)
0,1,1,2,3,5,8,13......
他和动态规划有什么关系？
首先，他有一个边界条件，就是f(0)=0,f(1)=1，相当于它不是从正无穷到负无穷都有定义的数列
像这种规定好的条件，我们把它叫做 边界条件（不依赖其他值就能直接得到）
f(n)=f(n-1)+f(n-2)
f(n)的值依赖于前两项斐波那契数列的值
这个式子就叫做动态规划中的 转移方程
每一个f(0),f(1),....,f(n)就叫做动态规划中的 状态
无后效性等价于有向无环图（DAG）这里先暂时不提
对于一个动态规划题，我们只需要确定状态，边界条件，转移方程，剩下的就只剩下写代码了
有三种不同的写法
1.顺着推
2.倒着推
（名字起得好随意，其实就是递推和递归）
3.记忆化搜索
int n,f[233]; int main() { cin>>n; f[0]=0; f[1]=1; for(int a=2;a<=n;a++) { f[a]=f[a-1]+f[a-2]; } cout<<f[n]; }
数组f代表状态，f(i)代表第i项
先定义边界状态
然后写转移方程
这是逆着推
for(int a=0;a<n;a++) { f[a+1]+=f[a]; f[a+2]+=f[a]; } cout<<f[n];
顺着推
想f(a)会影响那些斐波那契的值
int dfs(int n) { if(n==0) return 0; if(n==1) return 1; return dfs(n-1)+dfs(n-2); } int main() { cin>>n; cout<<dfs(n)<<endl; return 0; }
逆着推是当你算f(a)的时候，你要去算他
顺着推是当你算好f(a)的时候，你用f(a)去更新别人
两种写法在某些时候会有复杂度的区别
记忆化搜索
记忆化搜索的核心是搜索
以斐波那契数列为例：
如果我们直接搜索，搜到1就返回1，搜到0就返回0的话，这个代码的复杂度是f(f(n))，因为f(n)是由一个一个f[1]=1累加起来的
斐波那契通项公式是指数级的，所以当n很大时，复杂度就gg
记忆化：
int f[n]; bool suan_le_mei[n]; int dfs(int n) { if(n==0) return 0; if(n==1) return 1; if(suan_le_mei[n]) return f[n]; suan_le_mei[n]=true; f[n]=dfs(n-1)+dfs(n-2); } int main() { cin>>n; cout<<dfs(n)<<endl; return 0; }
因为当你算f(n)时要算f(n-2)，算f(n-1)时也要算f(n-2)，但是由于f(n-2)的值不变，所以它重复了
记忆化搜索就是保证每一个f(n)在搜索中只被算一次
所以我们两个数组
一个表示第i项的值
一个表示第i项有没有被算过
为了避免重复计算，我们要先看它有没有被算过
一旦算过就直接返回这一项的值
否则就先把它标记为算过，再dfs前两项计算这一项的值
这样写的话复杂度就变成了O(n)，因为每个值只被算了一次
一般来说它用不上，但是要知道怎么写
矩阵优化的话复杂度就变成了O(log n) 链接
常见的动规种类：
数位DP
树形DP
状压DP
区间DP
其他DP（其他是个什么鬼呦~）
还有两种NOIP中基本不会涉及
插头DP
博弈论DP
一般来说每一年NOIP中至少会出一道DP题
但是令人吃鲸的是：最大概率考的是其他DP（鬼才出题人）
先来看四种有套路的
数位DP：
看一个非常简单的题
读入两个正整数l，r，问你从l到r中有多少个正整数
答案显然是r-l+1
（但是我们要挑战自己，所以来个数位dp
[l,r]数的个数=[0,r]数的个数-[0,l-1]数的个数
我们就把问题化成了求[0,x]这段区间之间有多少个数
把x的十进制表示写出来
X=XnXn-1....X0
数位dp的核心思想就是按照十进制位从高到低一位一位进行dp
刚才的问题等价于看有多少个v满足0≤v≤x
V=VnVn-1...V0
如果有Vn=0就说明有前导0
给VnVn-1...V0每一个数填上0~9之间的某一个看有多少方案满足v≤x
数位dp填数的时候是从高往低填的
比如当你填Vn-3时，Vn-2，Vn-1,Vn已经填好了
比较两个数的大小从高往低比较
我们希望填上Vn-3后，v的前四位≤x的前四位
分情况讨论：
1.x前三位＞v前三位，此时Vn-3可以填0~9的任何一个数
2.x前三位=v前三位，为了保证填了这一位有v的前四位≤x的前四位，我们能填的数就是0~Xn-3
数位dp的数组一般至少有两个维度
f[i][j]
i表示已经填到了第i位
j取值要么是0，要么是1
j=0：表示x的前i位数＞v的前i位数
j=1：表示x的前i位数=v的前i位数
f[i][j]表示这种情况下的方案数
转移：我们去枚举第i-1位填什么，然后就转移到f[i-1][j']上
这就是数位dp的一个核心思路
代码奉上：
1 int solve(int x) 2 { 3 int n=0; 4 while(x) 5 { 6 z[n]=x%10; 7 x/=10; 8 n++; 9 } 10 n--; 11 12 memset(f,0,sizeof(f)); 13 14 f[n+1][1]=1; 15 16 for(int a=n;a>=0;a--) 17 { 18 for(int b=0;b<=1;b++) 19 { 20 if(b==0) 21 { 22 for(int c=0;c<=9;c++) 23 f[a][0]+=f[a+1][b]; 24 } 25 else 26 { 27 for(int c=0;c<=z[a];c++) 28 { 29 if(c==z[a]) f[a][1]+=f[a+1][b]; 30 else f[a][0]+=f[a+1][b]; 31 } 32 } 33 } 34 } 35 return f[0][0]+f[0][1]; 36 } 37 38 int main() 39 { 40 cin>>l>>r; 41 cout<<solve(r)-solve(l-1)<<endl; 42 return 0; 43 }
注意这里要进行两次dp，所以进行下一次dp之前要请空数组
我们发现当填第n位时，要从第n+1位转移过来
但是n+1位都是0，所以他们相等
所以我们令f[n+1][1]=1
考虑从第n位到第a+1位是相等还是小于
然后分情况讨论，枚举0和1
如果b=0，第a位就可以填0~9的任何一个数
如果b=1，第a位就可以填0~z[a]之间的数
然后再次讨论填的数是否=z[a]
答案是小于的方案加上等于的方案
Problem 2
求在[l,r]中的数的数位之和
把之前的代码稍微改一下
代码：
int l,r,z; int f[23333][2]; int g[23333][2]; int solve(int x) { int n=0; while(x) { z[n]=x%10; x/=10; n++; } n--; memset(f,0,sizeof(f)); memeste(g,0,sizeof(g)); f[n+1][1]=1; g[n+1][1]=0;//因为第n+1位是0 for(int a=n;a>=0;a--) { for(int b=0;b<=1;b++) { if(b==0) { for(int c=0;c<=9;c++) { f[a][0]+=f[a+1][b];//每一个方案对数位之和贡献一个c g[a][0]+=g[a+1][b]+f[a+1][b]*c; } } else { for(int c=0;c<=z[a];c++) { if(c==z[a]) { f[a][1]+=f[a+1][b]; g[a][1]+=g[a+1][b]+f[a+1][b]*c; } else { f[a][0]+=f[a+1][b]; g[a][0]+=g[a+1][b]+f[a+1][b]*c; } } } } } return g[0][0]+g[0][1]; } int main() { cin>>l>>r; cout<<solve(r)-solve(l-1)<<endl; return 0; }
改造改造就好了
Problem 3
求在[l,r]中满足十进制位中相邻两个数字之差至少为2的数有多少个
既然多了一个条件，最直接的方法就是增加一个维度，变成一个三维状态
f[i][j][k]
i和j一样
k表示第i位填了k
保证第i位和第i+1位的差至少为2
洛谷P2657 windy数
树形dp
举一个栗子:
给你一颗n个点的树，问这棵树有多少个点？、
显然是n个点
（但是我们要挑战自己，所以我们选择用树形dp
（显然是闲得蛋疼）
对于树形dp来说，这棵树一定会有一个根
不能再往下走的点就是叶子节点
以某个点为根的子树就是它能到达的所有点形成的树
以根节点为根的子树所对应的显然就是整棵树
f[i]代表以i为根的子树有多少个点
如果根节点是1的话，我们最终要求的显然就是f[1]
边界条件？f[leaf]=1 叶子节点所对应的子树大小就是1
显然它是从下往上推的
所以我们在算到p的时候，他下面的都已经被算完了
f[p]=f[son1]+f[son2]+...+f[sonk]+1（k为儿子的个数）
以p为根的子树大小=它所有儿子的子树大小之和+1
伪代码：
int f[233]; void dfs(int p) { for(x is p''s son)//枚举x是p的儿子 { dfs(x); f[p]+=f[x]; } f[p]++; } int main() { cin>>n;//点数 read_tree();//读入树 //由于它是从下往上，所以我们选用dfs dfs[1]; cout<<f[1]<<endl; return 0; }
又一个栗子：
给你一个n个点的树，求它的直径
直径：在这棵树上找到两个点，使它们的距离最远
考虑一棵子树内的直径怎么算
从一个点走到另一个点的过程尽可能大
树状路径一定是向上走到某一个点，在向下走到某一个点
从一个点向下走两条路，两条路拼起来后形成一条路径
要让这两条路径都尽可能长
也就是从一个点向下走最长和次长的路径拼起来，就是以这个点为拐点的最长路径
f[i][0]代表i向下最长路径的长度
f[i][1]代表i向下次长路径的长度
算一个点的答案，要把它所有儿子的答案整合起来
f[p][0]=max(f[p1][0],f[p2][0],...f[pk][0])+1
假如最大是p2
如果我们把f[p2][0]换成f[p2][1]可以吗？
不行！
因为如果f[p1][0]最长，f[p2][1]次长，就会重复走，这显然是不合法的
我们不如直接把它去掉
f[p][1]=max(f[p1][0],,...f[pk][0])+1
区间dp
洛谷P1880 合并石子
有n堆石子，你只能合并相邻两堆石子
a1,a2,a3,....,an
合并一次 n-1 堆石头
合并两次 n-2 堆石头
求最小代价
合并相邻，把所有的合并为一个：区间dp
状态一定是f[l][r]，代表把l和r合并的最小代价
让我们回到这个题
这个题求的是f[1][n]
先定义状态：f[l][r]
边界：f[i][i]=0当你只有一堆石头时，合并代价是0
最后一次合并一定是把两堆石头合并成一堆石头
合并石头并不会改变原本的顺序，所以最后一次合并一定可以找到一条分界线，使得左边为l，右边为r
合并左边：f[l][p] 合并右边：f[p+1][r]
转移方程:f[l][r]=min(f[l][p]+f[p+1][r]+sum[l][r])
思路：枚举断点
代码：
int z[manx],f[maxn][maxn]; int main() { cin>>n; for(int a=1;a<=n;a++) cin>>z[a];//表示石子数 memset(f,0x3f,sizeof(f));//初始化为无穷大 for(int a=1;a<=n;a++) f[a][a]=0; //枚举左端点，右端点，断点 for(int l=1;i<=n;l++)//枚举左端点 { for(int r=l+1;r<=n;i++)//枚举右端点 { for(int p=l;p<r;p++) { f[l][r]=min(f[l][r],f[l][p]+f[p+1][r]+sum[l][r]); //左边合并的代价+右边合并的代价+这段区间的石子之和 } } } cout<<f[1][n]<<endl; return 0； }
石子之和用前缀和计算就好了
代码非常的简单易懂对吧
但是
这是不对的！
(惊不惊喜，意不意外，刺不刺激
为什么呢？
因为它不满足dp的阶段性
因为你算f[1][n]时要用到f[2][n]，但它还没有被算过
我们注意到长的区间都是由短的区间拼起来的，所以我们枚举区间长度
int z[manx],f[maxn][maxn]; int main() { cin>>n; for(int a=1;a<=n;a++) cin>>z[a];//表示石子数 memset(f,0x3f,sizeof(f));//初始化为无穷大 for(int a=1;a<=n;a++) f[a][a]=0; for(int len=2;len<=n;len++)//枚举区间长度 { for(int l=1,r=len;r<=n;l++,r++)//枚举区间位置 { for(int p=l;p<r;p++) { f[l][r]=min(f[l][r],f[l][p]+f[p+1][r]+sum[l][r]); //左边合并的代价+右边合并的代价+这段区间的石子之和 } } } cout<<f[1][n]<<endl; return 0； }
复杂度O(n^3)
但是第1堆和第n堆是相邻的
怎么处理？
如果直接在最后一堆后面再加上一个第一堆石头，这样答案就不一定是f[1][n]了
它还有可能是f[2][n+1]
就是min(f[1][n],f[2][n+1])
但是这样a1和a2就不相邻了
在最后再加上a2
这样继续下去，把石子弄成a1,a2,....,an,a1,a2,....,an
ans=min(f[1][n],f[2][n+1],f[3][n+2],f[4][n+3]....)
每次合并两个相邻的东西相当于去掉一条边
只需要合并n-1次，这样的话至少有一条边没有用到，可以看成把这条边断开，就变成了断开的答案
所以我们刚才就是在枚举到底断开哪一条边
仍然是一遍dp，只不过区间变成了两边