Minimum Insertions to Form a Palindrome

Given a string S, your task is to determine the minimum number of insertions required to transform S into a palindrome. An insertion can be performed at any position in the string. There is no limit on the number of insertions. Use dynamic programming to compute the answer efficiently.

The problem can be formulated using the following recurrence relation:

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

For example, for S = "leetcode", the minimum number of insertions required is 5.

inputFormat

The input is read from stdin as a single line containing the string S (with a length between 1 and 1000).

outputFormat

Output a single integer representing the minimum number of insertions required to transform S into a palindrome. The output should be written to stdout.

## sample

ab

1

</p>