Calculate line cost corresponding to the above calculated extra spaces . The value lc [ i ] [ j ] indicates cost of putting words from word number i to j in a single line
for ( i = 1 ; i <= n ; i ++ ) { for ( j = i ; j <= n ; j ++ ) { if ( extras [ i ] [ j ] < 0 ) lc [ i ] [ j ] = INF ; else if ( j == n && extras [ i ] [ j ] >= 0 ) lc [ i ] [ j ] = 0 ; else lc [ i ] [ j ] = extras [ i ] [ j ] * extras [ i ] [ j ] ; } }