Pseudo-code for Computing DP and split
The example from the previous sections shows that we need DP[i] and split[i] for all words in our input array to get the solution for text justification. The pseudo-code for computing DP and split is given below. You can optimize the pseudo-code by cutting down iterations of the for loop in Step 4 by ending the loop if for any j value the misFit is :
xxxxxxxxxx29
Routine: getDPInput: index iOutput: DP[i] and split[i]Assumption: DP array initialized to -1 before calling this routine for each index​Base case 1: index exceeds bounds if (i >= n)1. return 0;​Base case 2: dp already calculated use memoization (dp[i] != -1)1. return dp[i];​Recursive case:1. min = infValue2. minInd = 03. misFit=0 //cost function4. for j=i..(n-1) a. misFit = f(i,j)+getDP(j+1) b. if (misFit < min) { min = misFit minInd = j }5.dp[i] = min;6.split[i] = minInd;7.return dp[i], split[i]OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
