优化
优化
复杂度理论
动态规划的时间复杂度
O(状态总数*每个状态的处理耗费)=O(状态总数*决策数)
空间优化
滚动数组
条件：如果状态依赖关系只在相邻的层之间，则滚动数组可以让空间复杂度降维
一般的，数组开依赖的相邻层数+1
数字三角形的状态转移方程为
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+A[i][j]]滚动数组优化之后为
dp[i%2][j]=min(dp[(i-1)%2][j],dp[(i-1)%2][j-1]）+A[i][j]特殊的，如果只依赖上一层，且方向是单向的，则可以直接无需这一维度
需要注意转移的顺序，正着还是反着（取决于是否可以用这一层的结果）
注意
不可以两个维度一起滚动
滚动数组滚动的是第一重循环的变量，而不是第二重甚至第三重
滚动数组只能滚一个维度，不能两个维度一起滚动
好处
节省空间
可以简化初始化边界
因为-1和-2这些空间都有了，可以把这些地方也用递推公式统一起来了
可以省去第一维度的情况
- 每个状态只依赖于其左边和上方的状态：如果状态转移方程中的每个状态只依赖于其左边和上方的状态，而不依赖于其他位置的状态，那么可以考虑省去第一维度。
- 状态之间的计算顺序没有依赖关系：如果状态之间的计算顺序没有依赖关系，即可以按照从左到右、从上到下的顺序计算每个状态，那么可以省去第一维度。
如果状态只能从上一行，不能从同一行转移，则高维度应该都倒顺序计算。
为什么要倒序循环呢？在去掉第一个维度后，若正序循环x1和x2,在计算f[x1][x2]时，转移来源f[x1'][x2']的值已经被覆盖（因为x1'≤x1以及x2'≤x2）,这意味着f[x1'][x2']实际对应的是f[k][x][x2]。
若倒序循环，则可消除该错误，这种方式保证计算f[x1][x2]时，转移来源f[x1'][x2']的值尚未被覆盖，实际对应的是f[k-1][x1'][x2']，从而保证转移方程与去掉维度前一致。
不可以省去第一维度的情况
- 状态之间存在横跨多行的依赖关系：如果状态之间存在横跨多行的依赖关系，即某个状态的计算依赖于当前行和前一行的状态，那么通常不能省去第一维度。
- 状态之间的计算顺序有依赖关系：如果状态之间的计算顺序有依赖关系，即某个状态的计算需要先计算其他状态，那么通常不能省去第一维度。
总体来说，省去第一维度的前提是能够保证状态之间的计算是可按行依次进行的，而不需要横跨多行或有特定的计算顺序。在一些问题中，这样的优化可以有效减少空间复杂度，提高算法的效率。但在某些情况下，为了保持问题的一般性和可读性，可能选择保留第一维度。
例题
eg. Backpack, lcis, paint house
fib
f[i%3]=f[i-1%3]+f[i-2%3]
时间优化
辅助结构
前缀和/后缀和
单调栈
单调队列
优先队列
线段树/树状数组
字典树优化
数学
k堆石子合并问题
石子归并的四边形优化
矩阵快速幂
状态优化
避免重复信息
eg. 状态压缩dp，不需要阶段信息，因为mask里面1的个数/最高位1的位置就是阶段
状态和答案交换位置
有的时候，状态这一维度太大，放答案合适
有的时候，不能直接正着推，只能翻着推
eg.
专题：把 X 变成 Y
部分题目也可以用 BFS 解决。
- 可怜的小猪
- 整数替换
- 使 X 和 Y 相等的最少操作次数 1795
- 转化数字的最小运算数 1850
- 坏了的计算器 1909
- 吃掉 N 个橘子的最少天数 2048