在dp阶段增长过程中，当决策范围每次只扩大、不缩小时，那就可以仅用一个变量维护最值。

在复杂情况下，可以用到数据结构进行维护决策的候选集合。

例1：

用 $n$ 张贴纸覆盖一段长度为 $m$ 的丝带，每张丝带可以覆盖 $[L_i,R_i]$ ，价格为 $c_i$ ，求最小花费。

可以得到转移方程：
$$
dp[r_i]=\underset {l_i\leq x\leq r_i}{min}dp[x]+c_i
$$
$dp[x]$ 表示覆盖 $[1,x]$ 的最小花费。注意到此题本质即为求 $l_i\leq x\leq r_i$ 的最小值 $dp[x]$ ，那么可以用线段树维护最小值，每次查询即可。

例2：

给定长度为 $n$ 的数组，求有多少个严格递增子序列长度为 $m$ 。

可以得到转移方程：
$$
dp[i,j]=\sum_{k<j&&a_k<a_j}dp[i-1,k]
$$
$dp[i,j]$ 表示以 $a_j$ 结尾的长度为 $i$ 的子序列。普通dp需要三重循环，但是可以优化：

设 $val(x)$ 表示 $x$ 离散化之后的值，对每一个 $i$ ，在 $[1,N-1]$ 上建立树状数组；对于插入操作，执行 $add(val(a_k),dp[i-1,k])$ ，对于查询操作，执行 $dp[i,j]=ask(val(a_j)-1)$ 。

要尽量分离dp决策的限制条件，分离内外层循环，在内层循环时将外层循环看成定值。