Exercise 4.3. A palindrome is a word (string) that reads the same from left to right as from right to left. For example, the string "NeverOddOrEven" is a palindrome. Every string can be partitioned in a number of palindromes. For example, the string "none" could be partitioned into four palindromes: "n" + "o" + "n" + "e", but of course, we could also partition it into only two palindromes: "non" + "e". Given a string s, we are interested in finding the minimum number of palindromes from which we can construct s. For the string "none", the minimum number is 2 and for the string "bobseesanna" the minimum number of palindromes would be three: "bob" + "sees" + "anna". a. Describe a dynamic programming algorithm that, given a string s, finds the minimum number of palindromes from which s can be constructed. You are not required to find the sequence of palindromes itself, only the number of palindromes that are needed. 6 Give a good description in words of the function(s) that you want to compute. Show how to initialize them, how to recursively compute their values, and where to find the optimal solution value. b. Analyze the running time of your algorithm. Is this bounded by a polynomial in the size of the input