讲师：钟皓曦，NOI2012Au，from 成都七中
听课能听懂 30% 就算成功**
dp
关键：状态、转移、初始化
转移：状态与状态之间的关系
初始化：状态的边界条件
数字三角形
状态：\(f_{i,j}\) 表示走到 \(a_{i,j}\) 这个位置的最大价值。
如何设计状态？
题目要你干什么——从第一行走到最后一行
该过程中什么在变化——位置、价值
题目求什么——最大价值
一般情况下状态表示形式：\(f[\text{除题目所求外所有在变化的量}]=\text{题目所求}\)。
如果每次走还有能量的花费，怎么定义状态？
再加一维，表示能量（能量在变化）。
先不要管维度是不是太多，先扔进去
维度少了，是做不了题的；维度多了，可以慢慢删
数字三角形2 noip.ac 2106
设定基本类似，目标：使得经过的所有数之和 %100 之后最大。
考虑刚才的状态能不能做这道题。
显然不能。不满足最优子结构。
反例：
1
50 97
1
2
dp 本质上类似贪心。
发现做不了——维度不够。
维度从哪找——变化的量。
先不要关注时空限制，保证答案正确。
变化的量——位置、%100 之后的价值
状态：\(f[i][j][k]\) 表示走到 \((i,j)\) 这个位置是否能达到 \(k\) 的价值。
斐波那契数列
求 \(f_n\% (10^9+7)\)，\(n\le 100\)。
有几种暴力写法？
两种——用别人更新自己（递推），用自己更新别人
dp 时要根据题目选择用哪一种。
比如，\(f(i)=\max\limits_{l\le j\le r}f_j+a_i\)，只能用别人更新自己。
除了数据结构优化 dp 的题，大部分两种写法都可以。
第三种写法——记搜，博弈论dp中常用
f[n]=dfs(n-1)+dfs(n-2)
复杂度 \(O(f(n))\)。
从组成表示来理解。
利用记忆化优化，用 \(g_i\) 表示是否已经求出 \(f_i\)。
复杂度 \(O(n)\)。
\(g_i\) 只会有一次 \(0\rightarrow 1\)。
前置知识结束
对 dp 分类——背包、区间、树形、数位、状压、插头、排列、博弈、一般
除了一般 dp 外，都有固定的状态设计和转移方程的写法。
最难的——数位 dp，没有套路。
ppt 108 P1 HDU5009
发现对一个位置修改多次没有意义，并且先染左边和先染右边没有区别。
于是定义从左到右进行染色。
顺序在 dp 上很重要。
\(f_i\) 表示 \(1\sim i\) 全都染完色的最小代价。
\(f_i=\min\limits_{1\le j<i}(f_j+diff(j+1,i)^2)\)。
时间复杂度 \(O(n^2)\)。
\(ans\le n\)（一个一个改）。
换句话说，选择的区间不能超过 \(\sqrt{n}\)。
即 \(diff(j+1,i)\le n\sqrt{n}\)。
枚举 \(\sqrt{n}\) 个位置。
发现决策单调性。
用 \(\sqrt{n}\) 个双指针维护这 \(\sqrt{n}\) 个位置。
时间复杂度 \(O(n\sqrt{n})\)。
标签：状态,le,复杂度,day3,sqrt,寒假,维度,dp,2.4 From： https://www.cnblogs.com/BYR-KKK/p/18005605