Максімальная вагавая трансфармацыя дадзенага радка


Узровень складанасці серада
Часта пытаюцца ў амазонка BlackRock ByteDance CodeNation DE Шоу 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

Тлумачэнне:

Ёсць чатыры магчымасці для радка "АА", пераўтварыць у які:

АВ → 2 - 1 = 1

БА → 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) прасторы.