Берілген жолдың салмақты максималды түрлендіруі


Күрделілік дәрежесі орта
Жиі кіреді Amazon BlackRock ByteDance CodeNation DE Шоу Expedia JP Morgan Ola Cabs
Динамикалық бағдарламалау String

Проблемалық мәлімдеме

Берілген жолдық есептің салмақты максималды түрлендіруі тек 'А' және 'В' екі таңбадан тұратын жол берілгендігін айтады. Бізде кез-келген символды ауыстырып қосу арқылы жолды басқа жолға айналдыру мүмкіндігі бар. Осылайша көптеген түрлендірулер мүмкін. Барлық мүмкін түрлендірулердің ішінен ең үлкен салмақ түрлендіруінің салмағын анықтаңыз.

Алгоритм

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

Түсіндіру:

«АА» жолының төрт мүмкіндігі бар, оны түрлендіруге келесілер кіреді:

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)

Мұнда біз DP үшін 1D массивін қолдандық, осылайша алгоритм O (N) кеңістігіне ие.