Minimum insertions to form a palindrome | DP | 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 .
function findMinInsertionsDP ( str , n ) { let table = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { table [ i ] = new Array ( n ) ; } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { table [ i ] [ j ] = 0 ; } } let l = 0 , h = 0 , gap = 0 ; 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 ] ; } let str = " " ; document . write ( findMinInsertionsDP ( str , str . length ) ) ;