მოცემული სტრიქონის მაქსიმალური წონის ტრანსფორმაცია


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon BlackRock ByteDance CodeNation დე შოუ Expedia JP Morgan ოლა კაბინები
დინამიური პროგრამირება სიმებიანი

პრობლემის განცხადება

მოცემული სიმების პრობლემის მაქსიმალური წონის ტრანსფორმაცია აცხადებს, რომ მოცემულია სიმები, რომელიც შედგება მხოლოდ ორი სიმბოლოსგან 'A' და 'B'. ჩვენ გვაქვს ოპერაცია, სადაც შეგვიძლია სტრიქონი სხვა სიმებად გადავაქციოთ ნებისმიერი სიმბოლოს გადართვით. ამრიგად, მრავალი გარდაქმნაა შესაძლებელი. ყველა შესაძლო გარდაქმნიდან გაირკვეს წონის მაქსიმალური გარდაქმნის წონა.

ალგორითმი

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

მაგალითიმოცემული სტრიქონის მაქსიმალური წონის ტრანსფორმაცია

BA
2

განმარტება:

სიმძლავრე ”AA” - ს ოთხი შესაძლებლობა არსებობს, რომელთა გარდაქმნაში შემდეგია:

AB 2 - 1 = 1

BA 2 - 1 = 1

AA 2

BB 2

რადგან ყველა ეს გარდაქმნა ერთნაირია, ჩვენ შეგვიძლია ავირჩიოთ შესაძლო გარდაქმნებიდან რომელიმე.

BAA
3

განმარტება: სულ არის 8 გარდაქმნა, რომელთაგან მაქსიმალური მნიშვნელობა აქვს ერთი წყვილისა და ერთი სინგრის მქონე გარდაქმნებს.

 

მიდგომა მოცემული სტრიქონის მაქსიმალური წონის ტრანსფორმაციისთვის

გულუბრყვილო მიდგომა

ჩვენ ყველა შესაძლო გარდაქმნას ვაკეთებთ თითოეული პერსონაჟის გადართვით. ყველა გარდაქმნის განხორციელების შემდეგ ვხვდებით თითოეული გარდაქმნის მნიშვნელობას და შემდეგ ვიპოვით მაქსიმალურ მნიშვნელობას თითოეული გარდაქმნის მნიშვნელობის გამოთვლით.

ეფექტური მიდგომა

ჩვენ გამოვიყენებთ რეკურსიას მოცემული სტრიქონის მაქსიმალური წონის ტრანსფორმაციის მოსაძებნად, გაანგარიშების შესამცირებლად გასხლის გამოყენებით. თუ ჩვენ ახლანდელი და მეორე სიმბოლოები განსხვავებული გვაქვს, ეს არის წყვილი. ამ შემთხვევაში, ჩვენ გვაქვს ორი ვარიანტი, ან ვცვლით პირველ სიმბოლოს და წინ ვწევართ, ან სიმბოლოებს არ ვცვლით და წინ გადავდივართ. სხვა პირობა იქნება, როდესაც ამჟამინდელი პერსონაჟი და იგივე სიმბოლოები იგივე გვაქვს. ამ შემთხვევაში, ჩვენ ჩავრთავთ სიმბოლოს და გავაკეთებთ მას წყვილს, ან არა და გავაგრძელებთ წინსვლას.

ვინაიდან თავდაპირველი (ან ორიგინალი) პრობლემა შეიძლება გადაკეთდეს უფრო მცირე ქვეპროპლიმებად, ჩვენ გამოვიყენებთ დინამიური პროგრამირება ქვეპროგრამების შენახვა და მათი შემდგომი გამოყენება.

კოდი

C ++ კოდი მოცემული სიმების პრობლემის მაქსიმალური წონის ტრანსფორმაციისთვის

#include<bits/stdc++.h>
using namespace std;

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}
AB
Enter pairCost and toggleCost
2 1
Maximum weight of a transformation of AB is 2

Java კოდი მოცემული სტრიქონის მაქსიმალური წონის ტრანსფორმაციისთვის

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}
AB 
Enter pairCost and toggleCost 
2 1
Maximum weight of a transformation of AB is 2

სირთულის ანალიზი

დროის სირთულე: O (N)

მას შემდეგ, რაც ჩვენ გამოვიყენეთ ალგორითმი, რომელიც იყენებს 1D DP- ს და გარდამავალი მდგომარეობაა ასევე O (1). ეს ალგორითმს აწარმოებს O (N) დროის სირთულეში.

სივრცის სირთულე: O (N)

აქ ჩვენ გამოვიყენეთ 1D მასივი DP– სთვის, ამრიგად, ალგორითმს აქვს O (N) სივრცის სირთულე.