AlgoDaily - Text Justification - Pseudo-code for Computing DP and split

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 $\infty$ :

xxxxxxxxxx
7.return dp[i], split[i]
 
Routine: getDP
Input: index i
Output: 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 = infValue
2. minInd = 0
3. misFit=0    //cost function
4. 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;

OUTPUT

Results will appear here.