动态规划空间优化为滚动数组优化，即对于一个多维数组，转移时均是由上一阶段转移来的，则可以将这一维省略，以降低空间复杂度，但要注意转移时的顺序；

0 - 1 背包问题

有一个最多能装 m m m 千克的背包，有 n n n 件物品，它们的重量分别是 W 1 ， W 2 ， . . . , W n W_1，W_2，..., W_n W1​，W2​，...,Wn​ ，它们的价值分别是 C 1 ， C 2 ， . . . ， C n C_1，C_2，... ，C_n C1​，C2​，...，Cn​ ；

若每种物品只有一件，问能装入的最大总价值；

由于最终价值与物品与重量有关，所以可定义状态， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 件物品装在容量为 j j j 的背包中所能装入的最大总价值；

依次遍历每一个物品与背包容量，比较取与不取当前物品的价值；

状态转移方程

d p [ i ] [ j ] = max ⁡ { d p [ i − 1 ] [ j ]    ( j < w [ i ] ) d p [ i − 1 ] [ j − w [ i ] ] + c [ i ] dp[i][j] = \max \begin{cases} dp[i- 1][j] \; (j < w[i]) \\ dp[i - 1][j - w[i]] + c[i] \end{cases} dp[i][j]=max{dp[i−1][j](jdp[i−1][0],dp[i−1][1]}dp[i][1]=j=i−kmaxi−1​{dp[j][0]−sum[j]+sum[i]} 时间复杂度为 O ( N ∗ N ) O(N * N) O(N∗N) ，考虑优化；

对于 d p [ i ] [ 1 ] dp[i][1] dp[i][1] 的方程，可将 s u m [ i ] sum[i] sum[i] 提出，得 d p [ i ] [ 1 ] = max ⁡ j = i − k i − 1 { d p [ j ] [ 0 ] − s u m [ j ] } + s u m [ i ] } dp[i][1] = \max_{j = i - k}^{i - 1}\{dp[j][0] − sum[j]\} + sum[i]\} dp[i][1]=maxj=i−ki−1​{dp[j][0]−sum[j]}+sum[i]} ，则可使用单调队列优化，维护一个递减单调队列；

依次遍历 n n n 个物品，若当前物品编号为 i i i 则，

先更新 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 的值；

将单调队列存储的候选优解中下标不满足 j j j 范围的从单调队列中删除；

用单调队列的队首元素更新 d p [ i ] dp[i] dp[i] 的值；

将下标 i i i 存入单调队列中，但为维护单调队列的单调性，应先将单调队列队尾元素中 d p dp dp 值小于 d p [ i ] dp[i] dp[i] 的元素从队列中删除，再将下标 i i i 存入单调队列；

所以在上述 1D/1D 的动态规划中，多项式 v a l ( i , j ) val(i, j) val(i,j) 是否能且仅能拆分为存在 q ( i ) , p ( j ) q(i), p(j) q(i),p(j) 两个部分是能否使用单调队列优化的基本条件；

即 d p dp dp 状态转移方程形如 d p [ i ] = min ⁡ j = L ( i ) R ( i ) { d p [ j ] + q ( i ) + p ( j ) } dp[i] = \min_{j = L(i)}^{R(i)}\{dp[j] + q(i) + p(j)\} dp[i]=minj=L(i)R(i)​{dp[j]+q(i)+p(j)} 可用单调队列优化；

在 1D/1D 的动态规划中，多项式 v a l ( i , j ) val(i, j) val(i,j) 若能拆分成 q ( i ) + p ( j ) + a ( i ) ∗ b ( j ) q(i) + p(j) + a(i) * b(j) q(i)+p(j)+a(i)∗b(j) 即可以使用动态规划的斜率优化；

其中， q ( i ) , a ( i ) q(i), a(i) q(i),a(i) 仅与 i i i 有关， p ( j ) , b ( j ) p(j), b(j) p(j),b(j) 仅与 j j j 有关；

即 d p dp dp 状态转移方程形如 d p [ i ] = min ⁡ j = L ( i ) R ( i ) { d p [ j ] + q ( i ) + p ( j ) + a ( i ) ∗ b ( j ) } dp[i] = \min_{j = L(i)}^{R(i)}\{dp[j] + q(i) + p(j) + a(i) * b(j)\} dp[i]=minj=L(i)R(i)​{dp[j]+q(i)+p(j)+a(i)∗b(j)} 可用斜率优化；

即可继续方程式变形， d p [ i ] = d p [ j ] + q ( i ) + p ( j ) + a ( i ) ∗ b ( j ) d p [ j ] + p ( j ) = − a ( i ) ∗ b ( j ) + d p [ i ] + q ( i ) \begin{aligned} dp[i] &= dp[j] + q(i) + p(j) + a(i) * b(j) \\ dp[j] + p(j) &= -a(i) * b(j) + dp[i] + q(i) \\ \end{aligned} dp[i]dp[j]+p(j)​=dp[j]+q(i)+p(j)+a(i)∗b(j)=−a(i)∗b(j)+dp[i]+q(i)​ 变形为 y = k x + b y = kx + b y=kx+b 的样式，其中 d p [ j ] + p ( j ) dp[j] + p(j) dp[j]+p(j) 即为 y y y ， b ( j ) b(j) b(j) 即为 x x x， − a ( i ) -a(i) −a(i) 即为 k k k ， d p [ i ] + q ( i ) dp[i] + q(i) dp[i]+q(i) 即为 b b b ；

则平面直角坐标系的一个点 ( b ( j ) , d p [ j ] + p ( j ) ) (b(j), dp[j] + p(j)) (b(j),dp[j]+p(j)) 仅与 j j j 有关，整个 d p dp dp 是一条直线，其斜率为 − a ( i ) -a(i) −a(i) ，截距为 d p [ i ] + q ( i ) dp[i] + q(i) dp[i]+q(i) ，由于要求 d p [ i ] dp[i] dp[i] 最小，则应让一条过点 ( b ( j ) , d p [ j ] + p ( j ) ) (b(j), dp[j] + p(j)) (b(j),dp[j]+p(j)) 的直线截距 d p [ i ] + q ( i ) dp[i] + q(i) dp[i]+q(i) 最小；

由于在求解 d p [ i ] dp[i] dp[i] 值时， − a ( i ) -a(i) −a(i) 仅与 i i i 有关，所以可以将其看作一个定值；

即求过点 ( b ( j ) , d p [ j ] + p ( j ) ) (b(j), dp[j] + p(j)) (b(j),dp[j]+p(j)) 的斜率为 − a ( i ) -a(i) −a(i) 的直线的截距 d p [ i ] + q ( i ) dp[i] + q(i) dp[i]+q(i) 最小；

若图上的每个点均为一个 j j j 所对应的点，直线为 l l l ，则此时情况为，

则点 C C C 即为 d p [ i ] dp[i] dp[i] 对应的最优的 d p [ j ] dp[j] dp[j] ；

则此时可以发现， A , B , C A, B, C A,B,C 三个点共同组成了一个下凸包，即 K l ( A , C ) < K l ( C , B ) K_{l(A, C)} < K_{l(C, B)} Kl(A,C)​