C++での特定の文字列の最大重み変換

• 指定された文字列の変換は、「AA」、「AB」、「BA」、および「BB」です。

• 最大ウェイト変換は「AB」または「BA」です。そして、重量は「1ペア-1トグル」=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