Minimum insertions to form a palindrome | DP | A Java 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 program to test above function .
import java . util . Arrays ; 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 ] : ( Integer . min ( table [ l ] [ h - 1 ] , table [ l + 1 ] [ h ] ) + 1 ) ; return table [ 0 ] [ n - 1 ] ; } public static void main ( String args [ ] ) { String str = " geeks " ; System . out . println ( findMinInsertionsDP ( str . toCharArray ( ) , str . length ( ) ) ) ; } }