Question 4.X[1 ... n] and Y[1 ... m] Strings (strings) are given. Our goal is with the least cost X[1 ... n] string Y[1 ... m] converting to string. Adding a new character costs up to TL, deleting an existing character It costs t dollars and converting an x character to a y character is f (x, y) dollars. Where k and t given positive integers, f (x, y) is a function with positive integers. a) (15 points) Write down the recurrence required to solve the problem with dynamic programming method. b) (20 points) Pseudo-code of the algorithm you designed with dynamic programming method (pseudo code) c) (15 points) Let k = 2, t = 1 and f (x, y) function given by the table below. (In this table the x variable column and y variable is given in the row.) By applying the algorithm you wrote down, calculate minmum cost to convert "ARABA" word to "Baar" word

AB R 00 2 2 2 2 A 1 0 2 1 4 B 1 2 0 4 1 1 1 4 0 4 R 1 4 1 4 0