【文件属性】：
文件名称：二分查找-dp之子序列
文件大小：529KB
文件格式：PPT
更新时间：2021-04-26 09:29:54
dp之子序列
二分查找
现在，我们仔细考虑计算dp[t]时的情况。假设有两个元素a[x]和a[y]，满足
(1)x < y < t (2)a[x] < a[y] < a[t] (3)dp[x] = dp[y]
此时，选择dp[x]和选择dp[y]都可以得到同样的dp[t]值，那么，在最长上升子序列的这个位置中，应该选择dp[x]还是应该选择dp[y]呢？
很明显，选择dp[x]比选择dp[y]要好。因为由于条件(2)，在a[x+1] ... a[t-1]这一段中，如果存在a[z]，a[x] < a[z] < a[y]，则与选择a[y]相比，将会得到更长的上升子序列。
再根据条件(3)，我们会得到一个启示：根据dp[]的值进行分类。对于dp[]的每一个取值k，我们只需要保留满足dp[t] = k的所有a[t]中的最小值。设D[k]记录这个值，即D[k] = min{a[t]} (dp[t] = k)。
注意到D[]的两个特点：
(1)D[k]的值是在整个计算过程中是单调不上升的。
(2)D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。