Максимална трансформација на тежината на дадена низа


Ниво на тешкотија Медиум
Често прашувано во Амазон Blackrock ByteDance CodeNation ДЕ Шо Expedia ЈП Морган Кабини Ола
Динамичко програмирање Стринг

Изјава за проблем

Максималната трансформација на тежината на дадениот проблем на низата вели дека дадена низа се состои само од два знака '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

објаснување:

Постојат четири можности за низата „АА“, во кои се претвораат следниве:

AB → 2 - 1 = 1

БА → 2 - 1 = 1

АА → 2

ББ → 2

Бидејќи сите овие трансформации тежат исто, можеме да избереме една од сите можни трансформации.

BAA
3

Објаснување: Вкупно има 8 трансформации, од кои трансформациите што имаат еден пар и еден единствен карактер имаат максимална вредност.

 

Пристап за максимална трансформација на тежината на дадена низа

Наивен пристап

Ние ги правиме сите можни трансформации со вклучување на секој карактер. Откако ги направивме сите трансформации, ја наоѓаме вредноста на секоја трансформација, а потоа ја наоѓаме максималната вредност со пресметување на вредноста на секоја трансформација.

Ефикасен пристап

Useе користиме рекурзија за да најдеме максимална трансформација на тежината на дадена низа, со користење на кастрење за да ги намалиме пресметките. Ако го имаме сегашниот карактер и вториот карактер различни, тоа е ова е пар. Во овој случај, имаме две опции или го менуваме првиот карактер и се движиме напред или не ги менуваме ликовите и се движиме напред. Другиот услов би бил кога имаме тековен карактер и втор карактер исти. Во овој случај, ќе го вклучиме ликот и ќе го направиме пар, или не и ќе продолжиме напред.

Бидејќи почетниот (или оригиналниот) проблем може да се претвори во помали подпроблеми, ние ќе го користиме динамично програмирање да ги зачувате подпроблемите и да ги користите понатаму.

Код

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

Анализа на сложеност

Временска комплексност: НА)

Бидејќи користевме алгоритам кој користи 1D DP, а транзицијата меѓу државите е исто така O (1). Ова го прави алгоритмот извршен во вкупната временска сложеност на O (N).

Комплексноста на просторот: НА)

Тука користевме 1D низа за DP, со што алгоритмот има сложеност на просторот O (N).