text: Minimum insertions to form a palindrome | DP | A Dynamic Programming based program to find minimum number insertions needed to make a string palindrome ; A utility function to find minimum of two integers ; 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 program to test above function .
code: #include <stdio.h> NEW_LINE #include <string.h> NEW_LINE int min ( int a , int b ) { return a < b ? a : b ; } int findMinInsertionsDP ( char str [ ] , int n ) { int table [ n ] [ n ] , l , h , gap ; memset ( table , 0 , sizeof ( table ) ) ; 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 ] : ( min ( table [ l ] [ h - 1 ] , table [ l + 1 ] [ h ] ) + 1 ) ; return table [ 0 ] [ n - 1 ] ; } int main ( ) { char str [ ] = " geeks " ; printf ( " % d " , findMinInsertionsDP ( str , strlen ( str ) ) ) ; return 0 ; }