algorithm - 字符串分区使得分区按递增顺序排列

Question

给出一串数字，例如，"12335457"。有效分区是字符串的分区，使得每个段都严格大于前一个段。

例如，"12 | 33 | 54 | 57" 是一个有效分区，57 > 54 > 33 > 12。另一个有效分区可以是 "12 | 335 | 457"。

给定字符串可能有多少个有效分区？字符串的最大长度可以是5000。

如果我们使用带有参数i和j的动态规划，这意味着最后一段是从i ...到..j，然后我们可以对剩余部分进行递归。

int solve(int i,int j) {
    // memoization need to be added
    int last_length = j - i + 1;
    int ans = 0;
    for(int k = j + last_length ; k < n ; k++) {
        if( segment(j+1,k) > segment(i,j) ) {   // this is possible in O(1) even if segment lengths are equal
                                                // we should do some pre preocessing on the given string
                                                // which can take O(n^2) time
                                                // if segment(j+1,k) length is more than L , then it is trivial
            ans += solve(j+1 , k);
        }
    }
}

但是这种方法需要 O(n^3) 时间。我们如何从 O(n^3) 减少它？

谢谢

Answer 1

我们可以有一个O(n^2) 算法。让 f(i, j, s) 表示有效分区的数量，直到以字符串 s 的第 i 个字符结束的段为止，并且向后扩展 j 个字符。然后:

f(i, j, s):
  # A segment extending all the way to the start
  if i + 1 == j:
    return 1

  # A one-character segment that's smaller
  # than the preceding character
  if j == 1 and s[i] <= s[i - 1]:
    return 0

  segment = s[i - j + 1...i]

  # Find longest preceding segment in O(1)
  longest = 
    a segment of length j extending back
    from s[i - j] or length (j-1) if the first
    segment was equal or larger than segment

  # Replace 'sum' with O(1) prefix sum calculation
  # since we can record that for each previous i
  # as we increase j
  return sum(f(i - j, k, s) for k = 1 to length(longest))