Максимальное преобразование веса данной строки
Опубликовано: 21 Января, 2022
Дана строка, состоящая только из A и B. Мы можем преобразовать данную строку в другую, переключая любой символ. Таким образом, возможны многие преобразования данной строки. Задача - найти вес максимального преобразования веса.
Вес укуса рассчитывается по следующей формуле.
Вес строки = Вес всего пар + вес одиночных знаков - Общее количество переключателей. Два последовательных символа считаются парой, только если они разные. Вес одной пары (оба символа разные) = 4 Вес одного символа = 1
Примеры :
Ввод: str = "AA" Выход: 3 Преобразования данной строки: «AA», «AB», «BA» и «BB». Максимальное преобразование веса - «AB» или «BA». И вес "Одна пара - один тумблер" = 4-1 = 3. Ввод: str = "ABB" Выход: 5 Преобразования: «ABB», «ABA», «AAB», «AAA», «BBB», «ББА», «БАБ» и «БАД» Максимальный вес исходной струны 4 + 1 (одна пара + 1 персонаж)
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Если (n == 1) maxWeight (str [0..n-1]) = 1 Иначе, если str [0]! = Str [1] // Максимум два случая: первый символ рассматривается отдельно // Первая пара рассматривается отдельно maxWeight (str [0..n-1]) = Max (1 + maxWeight (str [1..n-1]), 4 + getMaxRec (str [2..n-1]) Еще // Максимум два случая: первый символ рассматривается отдельно // Первая пара рассматривается отдельно // Поскольку первые два символа одинаковые, а переключатель - // требуется для формирования пары, вместо пары добавляется 3 // из 4 maxWeight (str [0..n-1]) = Max (1 + maxWeight (str [1..n-1]), 3 + getMaxRec (str [2..n-1])
If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. Since same suproblems are called again, this problem has Overlapping Subprolems property. So min square sum problem has both properties (see thisand this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems.
Below is a memoization based solution. A lookup table is used to see if a problem is already computed.
C++
// C++ program to find maximum weight // transformation of a given string #include<bits/stdc++.h> using namespace std; // Returns weight of the maximum // weight transformation int getMaxRec(string &str, int i, int n, int lookup[]) { // Base case if (i >= n) return 0; //If this subproblem is already solved if (lookup[i] != -1) return lookup[i]; // Don"t make pair, so // weight gained is 1 int ans = 1 + getMaxRec(str, i + 1, n, lookup); // If we can make pair if (i + 1 < n) { // If elements are dissmilar, // weight gained is 4 if (str[i] != str[i+1]) ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans); // if elements are similar so for // making a pair we toggle any of them. // Since toggle cost is 1 so // overall weight gain becomes 3 else ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans); } // save and return maximum // of above cases return lookup[i] = ans; } // Initializes lookup table // and calls getMaxRec() int getMaxWeight(string str) { int n = str.length(); // Create and initialize lookup table int lookup[n]; memset (lookup, -1, sizeof lookup); // Call recursive function return getMaxRec(str, 0, str.length(), lookup); } // Driver Code int main() { string str = "AAAAABB" ; cout << "Maximum weight of a transformation of " << str << " is " << getMaxWeight(str); return 0; } |
Java
// Java program to find maximum // weight transformation of a // given string class GFG { // Returns wieght of the maximum // weight transformation static int getMaxRec(String str, int i, int n, int [] lookup) { // Base case if (i >= n) { return 0 ; } // If this subproblem is already solved if (lookup[i] != - 1 ) { return lookup[i]; } // Don"t make pair, so // weight gained is 1 int ans = 1 + getMaxRec(str, i + 1 , n, lookup); // If we can make pair if (i + 1 < n) { // If elements are dissmilar, // weight gained is 4 if (str.charAt(i) != str.charAt(i + 1 )) { ans = Math.max( 4 + getMaxRec(str, i + 2 , n, lookup), ans); } // if elements are similar so for // making a pair we toggle any of // them. Since toggle cost is // 1 so overall weight gain becomes 3 else { ans = Math.max( 3 + getMaxRec(str, i + 2 , n, lookup), ans); } } // save and return maximum // of above cases return lookup[i] = ans; } // Initializes lookup table // and calls getMaxRec() static int getMaxWeight(String str) { int n = str.length(); // Create and initialize lookup table int [] lookup = new int [n]; for ( int i = 0 ; i < n; i++) { lookup[i] = - 1 ; } // Call recursive function return getMaxRec(str, 0 , str.length(), lookup); } // Driver Code public static void main(String[] args) { String str = "AAAAABB" ; System.out.println( "Maximum weight of a" + " transformation of " + str + " is " + getMaxWeight(str)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find maximum weight # transformation of a given string # Returns weight of the maximum # weight transformation def getMaxRec(string, i, n, lookup): # Base Case if i > = n: return 0 # If this subproblem is already solved if lookup[i] ! = - 1 : return lookup[i] # Don"t make pair, so # weight gained is 1 ans = 1 + getMaxRec(string, i + 1 , n, lookup) # If we can make pair if i + 1 < n: # If elements are dissimilar if string[i] ! = string[i + 1 ]: ans = max ( 4 + getMaxRec(string, i + 2 , n, lookup), ans) # if elements are similar so for # making a pair we toggle any of them. # Since toggle cost is 1 so # overall weight gain becomes 3 else : ans = max ( 3 + getMaxRec(string, i + 2 , n, lookup), ans) # save and return maximum # of above cases lookup[i] = ans return ans # Initializes lookup table # and calls getMaxRec() def getMaxWeight(string): n = len (string) # Create and initialize lookup table lookup = [ - 1 ] * (n) # Call recursive function return getMaxRec(string, 0 , len (string), lookup) # Driver Code if __name__ = = "__main__" : string = "AAAAABB" print ( "Maximum weight of a transformation of" , string, "is" , getMaxWeight(string)) # This code is contributed by vibhu4agarwal |
C#
// C# program to find maximum // weight transformation of a // given string using System; class GFG { // Returns wieght of the maximum // weight transformation static int getMaxRec( string str, int i, int n, int []lookup) { // Base case if (i >= n) return 0; //If this subproblem is already solved if (lookup[i] != -1) return lookup[i]; // Don"t make pair, so // weight gained is 1 int ans = 1 + getMaxRec(str, i + 1, n, lookup); // If we can make pair if (i + 1 < n) { // If elements are dissmilar, // weight gained is 4 if (str[i] != str[i + 1]) ans = Math.Max(4 + getMaxRec(str, i + 2, n, lookup), ans); // if elements are similar so for // making a pair we toggle any of // them. Since toggle cost is // 1 so overall weight gain becomes 3 else ans = Math.Max(3 + getMaxRec(str, i + 2, n, lookup), ans); } // save and return maximum // of above cases return lookup[i] = ans; } // Initializes lookup table // and calls getMaxRec() static int getMaxWeight( string str) { int n = str.Length; // Create and initialize lookup table int [] lookup = new int [n]; for ( int i = 0 ; i < n ; i++) lookup[i] = -1; // Call recursive function return getMaxRec(str, 0, str.Length, lookup); } // Driver Code public static void Main() { string str = "AAAAABB" ; Console.Write( "Maximum weight of a" + " transformation of " + str + " is " + getMaxWeight(str)); } } // This code is contributed by Sumit Sudhakar |
Javascript
<script> // Javascript program to find maximum // weight transformation of a // given string // Returns wieght of the maximum // weight transformation function getMaxRec(str, i, n, lookup) { // Base case if (i >= n) { return 0; } // If this subproblem is already solved if (lookup[i] != -1) { return lookup[i]; } // Don"t make pair, so // weight gained is 1 let ans = 1 + getMaxRec(str, i + 1, n, lookup); // If we can make pair if (i + 1 < n) { // If elements are dissmilar, // weight gained is 4 if (str[i] != str[i + 1]) { ans = Math.max(4 + getMaxRec(str, i + 2, n, lookup), ans); } // if elements are similar so for // making a pair we toggle any of // them. Since toggle cost is // 1 so overall weight gain becomes 3 else { ans = Math.max(3 + getMaxRec(str, i + 2, n, lookup), ans); } } // save and return maximum // of above cases return lookup[i] = ans; } // Initializes lookup table // and calls getMaxRec() function getMaxWeight(str) { let n = str.length; // Create and initialize lookup table let lookup = new Array(n); lookup.fill(0); for (let i = 0; i < n; i++) { lookup[i] = -1; } // Call recursive function return getMaxRec(str, 0, str.length, lookup); } let str = "AAAAABB" ; document.write( "Maximum weight of a" &nb
РЕКОМЕНДУЕМЫЕ СТАТЬИ |