int minInsertionsDP(String s){
  int n=s.length();
  int[][] dp=new int[n][n];
  for (int gap=1; gap < n; gap++) {
    for (int l=0, h=gap; h < n; l++, h++) {
      dp[l][h]=s.charAt(l) == s.charAt(h) ? dp[l + 1][h - 1] : Math.min(dp[l][h - 1],dp[l + 1][h]) + 1;
    }
  }
  return dp[0][n - 1];
}

int minInsertionsDP ( String s ) { int n = s . length ( ) ; int [ ] [ ] dp = new int [ n ] [ n ] ; for ( int gap = 1 ; gap < n ; gap ++ ) { for ( int l = 0 , h = gap ; h < n ; l ++ , h ++ ) { dp [ l ] [ h ] = s . charAt ( l ) == s . charAt ( h ) ? dp [ l + 1 ] [ h - 1 ] : Math . min ( dp [ l ] [ h - 1 ] , dp [ l + 1 ] [ h ] ) + 1 ; } } return dp [ 0 ] [ n - 1 ] ; }
dp , bottom - up fill a table in diagonal direction
