Minimum insertions to form a palindrome | DP | A C # solution for Dynamic Programming based program to find minimum number insertions needed to make a string palindrome ; A DP function to find minimum number of insertions ; Create a table of size n * n . table [ i ] [ j ] will store minimum number of insertions needed to convert str [ i . . j ] to a palindrome . ; Fill the table ; Return minimum number of insertions for str [ 0. . n - 1 ] ; Driver code
using System ; class GFG { static int findMinInsertionsDP ( char [ ] str , int n ) { int [ , ] table = new int [ n , n ] ; int l , h , gap ; for ( gap = 1 ; gap < n ; ++ gap ) for ( l = 0 , h = gap ; h < n ; ++ l , ++ h ) table [ l , h ] = ( str [ l ] == str [ h ] ) ? table [ l + 1 , h - 1 ] : ( Math . Min ( table [ l , h - 1 ] , table [ l + 1 , h ] ) + 1 ) ; return table [ 0 , n - 1 ] ; } public static void Main ( ) { String str = " geeks " ; Console . Write ( findMinInsertionsDP ( str . ToCharArray ( ) , str . Length ) ) ; } }