C ++中给定字符串的最大权重转换

问题陈述

给定一个仅包含A和B的字符串。我们可以通过切换任意字符将给定的字符串转换为另一个字符串。因此，给定字符串的许多转换都是可能的。任务是找到最大权重变换的权重。

ing的重量使用以下公式计算-

Weight of string = Weight of total pairs + weight of single characters - Total number of toggles.

• 仅当两个连续字符不同时，才将它们视为一对。

• 一对的重量（两个字符都不同）= 4

• 单个字符的权重= 1

如果输入字符串是-“ AA”，那么输出将是3-

• 给定字符串的转换为“ AA”，“ AB”，“ BA”和“ BB”。

• 最大重量转换为“ AB”或“ BA”。权重为“一对-一次切换” = 4-1 = 3。

算法

1. If (n == 1)
   maxWeight(str[0..n-1]) = 1
2. Else If str[0] != str[1]
   maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1])
3. Elses
   maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1])

示例

#include<bits/stdc++.h>
using namespace std;
int getMaxRec(string &str, int i, int n, int lookup[]){
   if (i >= n) {
      return 0;
   }
   if (lookup[i] != -1) {
      return lookup[i];
   }
   int ans = 1 + getMaxRec(str, i + 1, n, lookup);
   if (i + 1 < n) {
      if (str[i] != str[i+1]) {
         ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
      } else {
         ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
      }
   }
   return lookup[i] = ans;
}
int getMaxWeight(string str){
   int n = str.length();
   int lookup[n];
   memset(lookup, -1, sizeof lookup);
   return getMaxRec(str, 0, str.length(), lookup);
}
int main(){
   string str = "AA";
   cout << "Result = " << getMaxWeight(str) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它生成以下输出-

Result = 3