# Minimum Cost to Make Two Strings Identical

Given two strings **string1** and **string2** find the minimum cost required to make the given two strings identical. We can delete characters from both the strings. The cost of deleting a character from **string1** is **costX** and **string2** is **costY**. The cost of removing any characters from the same string is the same. Like, removing any

Input:
The first line contains integers costX and costY.
The second line contains the two strings X and Y.
Output:
Print the total cost to make the two strings
equal for each test case in a new line.
Constraints:
1<= length of strings X and Y <=1000
1<= costX, costY <=1000

**Explanation of Example:**

Input:
1
10 20
"acba" "acdb"
Output:
30
Explanation:
The similar strings would be "acb".
So need to remove one from string1 and one from string2
costing total of 30.

The problem can be solved recursively,

Let,

Let us consider, what can be cases that can arrive for F(i,j) where 0 <= i<n && 0 <= j<m

Case 1.string1[i]==string2[j] that is indexed characters are similar

In such a case, we don't need any additional cost to make strings similar, the cost will be similar to sub-problem of size i-1, j-1. This can be recursively written as

Case 2.string1[i]!=string2[j] that is indexed characters are not similar.

In such a case we need to invest,

This can be recursively written as,

This can be recursively written as,

This can be recursively written as, Finally, we would take minimum out of this three cases.

So here goes the problem structure,

Now the above recursion will create many overlapping subproblems and hence we need two converts it into DP.

Converting into DPC++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput