长者zhx来啦。。
（又要送冰红茶了。。。）
zhx一上来就讲动态规划。。。是不是要逼死人。。。。
动态规划：
最简单的例子：斐波那契数列。因为他是递推（通项公式不算）的，所以前面的已经确定的项不会影响后面的，满足无后效性，为最简单的动态规划。
3种写法：用算好的自己来算别人，或者用别人更新自己,记忆化搜索。
计算斐波那契数列f[n]=f[n-1]+f[n-2]。
如果用dfs来计算的话，在dfs函数里return dfs(n-1)+dfs(n-2);
由于没有记忆化，（没有把每一个阶段记录下来，）复杂度达到了f[n]级别而线性地推可以O（n）。
这就是为什么记忆化。
（zhx：我课件只有130页，没什么东西。。）
动态规划过程图
画成图就是dag有向无环图。
背包问题：洛谷p1048采药。
代码：
#include<iostream> #include<cstring> using namespace std; const int maxn = 3404; const int maxm = 12882; int main() { int N,W; int w[maxn],v[maxn],value[101][1001]; cin>>W>>N; for(int i=1;i<=N;i++) cin>>w[i]>>v[i]; memset(value,0,sizeof(value)); //value数组注意要清空 for(int i=1;i<=N;i++) for(int j=W;j>=0;j--) { if(j>=w[i]) value[i][j]=max(value[i-1][j],value[i-1][j-w[i]]+v[i]); else value[i][j]=value[i-1][j]; } cout<<value[N][W]<<endl; return 0;}
然后是无限背包，有限背包。
然后是区间dp，
例题为合并石子。
满足只能合并相邻的两个元素的题为区间dp。
代码：
状压dp：洛谷p1171
如果一个题数据n<=20||22，考虑状压dp。
洛谷p1879玉米田，状压dp；
P1896 [SCOI2005]互不侵犯，状压dp；
然后是数位dp：
P2657 [SCOI2009]windy数
。
树形dp：
题目：对于一棵有n个点的树，求它有多少个点。
（题目无锅）。
要求用树形dp做。
原理：处理子树。我们设f[i]表示i节点以及他的子树一共有多少个节点。那么转移方程为f[i]=Σf[j](子树)+1(自己);
最后输出f[1]；
博弈论dp： 明天再讲。