In Java!!!

Alignment 2 strings: insert gaps into both strings so that each character in one string is aligned with a gap, or the same character in the other string. Find the minimum cost.

Example, word1: kitchen word2: kitten

k i t - c h e n

k i t t - - e n

cost: 3

- - - - - - k i t c h e n

k i t t e n - - - - - - -

cost: 13

(a) Give a naive recursive way to solve this problem

(b) Use dynamic programming to solve this problem