[Pseudocode is acceptable -> dont need to write the entire program]

Include the following static method in the class DynamicProgramming

stringAlignment(String x, String y) . Assume that x is a string of length n and y is a string of length m such that n m. This method returns a string z (obtained by inserting $ at n m indices in y) such that AlignCost(x, z) AlignCost(x, z) over all possible z (obtained by inserting n m many $s in y). You may assume that length of x is at least the length of y and neither of x or y has the character $. Note that the length of the returned string z must equal the length of x.

You must use dynamic programming paradigm to arrive at your code. For this, first define the recurrence relation. Then arrive at an iterative solution. Your code must be iterative, not recursive and should not use use memoization.

Extra information on alignment

1.2 Alignment and b, we define a function penalty a, b as follows: if a eq 0. If a or b equals then penalty a, b) 4; otherwise penalty(a, b) 2. Given two strings z z122 rn and y yiyo yn alignment cost between r and y is AlignCost(z, y) X penalty (zi, yi i 1. Let r 122,... zn and y yiy2... ym two strings where n m. assume that neither string has the character S. Our task is to align the two strings. The alignment is done by creating a new string z formed by inserting the character at n m indices in y. Note that length of z is n. Note that there are many choices for 2. The goal is to find a z for which AlignCost(r,z) is minimized. We would like to write a method that gets two strings r (of length n) and y (of length m) as parameters (assume that n m) and computes a z such that AlignCost(z, z) S AlignCost(z, z') for every z' (obtained by inserting n m many S's in y)