Minimum insertions to form a palindrome | DP | A 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 " ; cout << findMinInsertionsDP ( str , strlen ( str ) ) ; return 0 ; }