c – 使用最少的操作将给定的字符串转换为已排序的字符串

Given string: dcba
We can convert this string into a sorted using at least 3 operations. The generated string can be any of the following:
dddd (3 operations)
aaaa (3 operations)
cccc (3 operations)
..
etc.

这个问题相当于你的字符串的 longest increasing subsequence：显然,保持最大字母数不变是最佳的,并且这些字母必须形成一个递增的子序列.另一个方向类似.

虽然LIS可以在一般序列的O(n log n)中求解,但您甚至不需要它,因为您手头有一个更简单的特殊情况,字母大小为a = 26.您可以使用动态编程来解决问题在O(n·a)：

设f(i,j)是以字母j结尾的前缀s [0 ..(i-1)]的最优解.我们已经复发了

f(0,j) = 0  for j = 0..25
f(i + 1,j) = [j != s[i]] + MIN(k = 0..j,f(i,k))

如果k！= j则[k！= j]为1,否则为0.通过顺序计算表的每一行(增加j),您可以计算O(1)中的最小值.

最终解是MIN(j = 0..25,f(n,j)).您可以通过递归跟随导致最佳解决方案的DP状态来构造相应的字符串：

const int a = 'z' - 'a' + 1;
vector<array<int,a>> f;
string s = "azbzc";

void reconstruct(int i,int j) {
  if (i == 0)
    return;
  int prev_j = min_element(begin(f[i-1]),begin(f[i-1]) + j + 1) - begin(f[i-1]);
  reconstruct(i - 1,prev_j);
  cout << (char)('a' + j);
}

int main() {
  f.resize(s.size() + 1);
  int n = s.size();
  for (int i = 0; i < n; ++i) {
    int sol = f[i][0];
    for (int j = 0; j < a; ++j) {
      sol = min(sol,f[i][j]);
      f[i+1][j] = (j != s[i] - 'a') + sol;
    }
  }
  int j = min_element(begin(f[n]),end(f[n])) - begin(f[n]);
  cout << "solution: " << f[n][j] << endl;
  reconstruct(n,j);
  cout << endl;
}

输出：

solution: 2
aabbc