在子序列问题中有一系列问题尤为经典,而将子序列问题加上一个连续的限制条件便转化为了子串问题,本文就这些经典问题进行总结性讨论。

最长上升子序列(LIS)

$$dp[i]= \max\limits_{1\leq j< i,value[i]>value[j]}(dp[j]+1) $$

利用序列长度作为阶段,状态为当前子序列长度,若满足序列条件则可以进行转移。

修改条件$value[i]>value[j]$易将问题转化为最长不上升子序列最长下降子序列以及最长不下降子序列。时间复杂度$O(|S|^2)$。

其中,关于LIS的问题可以看这篇文章:

同时,关于这一类问题还有使用树状数组的解法,其时间复杂度为$O(|S|\log |S|)$,可以参考这篇文章:

子串问题

暴力计算即可,时间复杂度$O(|S|)$。

最长公共子序列(LCS)

$$dp[i][j]=\begin{cases}dp[i-1][j-1] + 1,(s[i]==s[j]) \\ \max(dp[i-1][j],dp[i][j-1]),(s[i] != s[j]) \end{cases}$$

利用两个序列长度作为阶段,如果$s[i]==s[j]$,则将问题转化为其子问题$dp[i-1][j-1]$,也就是去除掉末尾的相同字符的序列求LCS,若$s[i]!=s[j]$,则考虑其LCS为$\max(dp[i-1][j],dp[i][j-1])$,也就是分别不考虑末尾字符的序列求LCS。

时间复杂度$O(|S_{1}||S_{2}|)$。

子串问题

$$dp[i][j]=dp[i-1][j-1]+1,(s[i]==s[j])$$

相较于LCS问题,由于施加了连续这样一个限制条件,在状态转移中将不再考虑$dp[i-1][j]$与$dp[i][j-1]$两种情况(这两种情况将破坏连续性)。

时间复杂度$O(|S_{1}||S_{2}|)$。

最长回文子序列(LPS)

$$dp[i][i+len]=\begin{cases}dp[i+1][i+len-1],(s[i]==s[i+len]) \\ \max(dp[i+1][i+len],dp[i][i+len-1]),(else)\end{cases}$$

亦可将问题理解为将序列反转,对原序列与反转序列求LCS。

时间复杂度$O(|S|^2)$。

子串问题

Manacher算法在$O(|S|)$的时间复杂度下可以很好地解决这个问题。

最大子序列

暴力即可,时间复杂度$O(|S|)$。

子串问题

$$dp[i]=\begin{cases}\max(\sum_{j=last}^{i-1}value[j]+value[i],dp[i-1]),(\sum_{j=last}^{i-1}value[j]>0) \\ value[i],(\sum_{j=last}^{i-1}value[j]<=0)\end{cases}$$

更直观的来说,对于当前位置$i$,若其前面的部分连续子序列和大于零,则加上当前$value[i]$,否则重置部分连续子序列和为$value[i]$,每次处理后对答案进行维护。时间复杂度$O(|S|)$

参考代码:

int max_substring(vector<int>& a) {
  int cur_max, ret;
  if ( a.size() < 2 )
        return a[0];
  cur_max = ret = a[0];
  for ( int i = 1; i < a.size(); ++i ) {
    if ( cur_max <= 0 )
      cur_max = a[i];
       else 
      cur_max += a[i];
    
    ret = max(cur_max, ret);
  }
  
  return ret;
}

当然,本文所总结的子序列(子串)问题知识只是其中的冰山一角,只要将问题稍加组合变换便可以组成一系列新的问题,如最大k子串最大k子序列最长公共回文子序列等,而求解这一系列问题并不全是机械式照搬结论,更多的是需要我们发挥创造力去具体地看待每一个问题。

Last modification:August 20th, 2020 at 01:04 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏