Minimum Operations to Make a Palindrome

You are given a string s. Your task is to determine the minimum number of operations required to transform s into a palindrome. In one operation, you can insert any character at any position in the string.

A string is a palindrome if it reads the same forwards and backwards. The solution is based on dynamic programming. Define dp[i][j] as the minimum number of insertions needed to convert the substring s[i...j] into a palindrome. The recurrence is given by:

$$\text{dp}[i][j]=\begin{cases} 0, & \text{if } i \geq j,\\ \text{dp}[i+1][j-1], & \text{if } s[i]=s[j],\\ \min(\text{dp}[i+1][j],\text{dp}[i][j-1])+1, & \text{if } s[i]\neq s[j]. \end{cases} $$

Compute dp[0][n-1] where n is the length of the string to obtain your answer.

inputFormat

The input consists of a single line containing the string s (with length at least 1 and at most 1000), composed of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of operations (insertions) required to transform s into a palindrome.

## sample

aab

1

</p>