Hello!

Could you help me with this exercise about Algorithms Design, please?

Given a string S = c1, c2,…,cn, determine the minimum number of characters that you must insert to S to make it a palindrome. A chain is palindromic if it remains the same when inverted. For example, if S is raro, the minimum number is 1.

Hint: You can build the Dynamic Programming solution, but a potentially shorter solution is to reduce that problem to an instance of a Dynamic Programming algorithm. If you take the second way of solving it, make sure to formally argue why it is correct.