子序列问题的二分查找-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]。