algorithm - Implementing Text Justification with Dynamic Programming -

i'm trying understand concept of dynamic programming, via course on mit ocw here. explanation on ocw video great , all, feel don't understand until implemented explanation code. while implementiing, refer notes lecture note here, particularly page 3 of note.

the problem is, have no idea how translate of mathematical notation code. here's part of solution i've implemented (and think it's implemented right):

import math  paragraph = "some long lorem ipsum text." words = paragraph.split(" ")  # count total length strings in list of strings. # function used badness function below. def total_length(str_arr):     total = 0      string in str_arr:         total = total + len(string)      total = total + len(str_arr) # spaces     return total  # calculate badness score word. # str_arr assumed send word[i:j] in notes # don't make , j argument since require # global vars then. def badness(str_arr, page_width):     line_len = total_length(str_arr)     if line_len > page_width:         return float('nan')      else:         return math.pow(page_width - line_len, 3) 

now part don't understand on point 3 5 in lecture notes. literally don't understand , don't know start implementing those. far, i've tried iterating list of words, , counting badness of each allegedly end of line, this:

def justifier(str_arr, page_width):     paragraph = str_arr     par_len = len(paragraph)     result = [] # stores each line list of strings     in range(0, par_len):         if == (par_len - 1):             result.append(paragraph)         else:             dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) j in range(i + 1, par_len + 1)]              # should min(dag), index, , declares end of line? 

but then, don't know how can continue function, , honest, don't understand line:

dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) j in range(i + 1, par_len + 1)]  

and how i'll return justifier int (since decided store return value in result, list. should make function , recurse there? should there recursion @ all?

could please show me next, , explain how dynamic programming? can't see recursion is, , subproblem is.

thanks before.

in case have trouble understanding core idea of dynamic programming here take on it:

dynamic programming sacrificing space complexity time complexity (but space use very little compared time save, making dynamic programming totally worth if implemented correctly). store values each recursive call go (e.g. in array or dictionary) can avoid computing second time when run same recursive call in branch of recursion tree.

and no not have use recursion. here implementation of question working on using loops. followed textalignment.pdf linked alexsilva closely. find helpful.

  def length(wordlengths, i, j):     return sum(wordlengths[i- 1:j]) + j - + 1   def breakline(text, l):     # wl = lengths of words     wl = [len(word) word in text.split()]      # n = number of words in text     n = len(wl)          # total badness of text l1 ... li     m = dict()     # initialization     m[0] = 0          # auxiliary array     s = dict()      # actual algorithm     in range(1, n + 1):         sums = dict()         k =         while (length(wl, k, i) <= l , k > 0):             sums[(l - length(wl, k, i))**3 + m[k - 1]] = k             k -= 1         m[i] = min(sums)         s[i] = sums[min(sums)]      # splitting working backwords     line = 1     while n > 1:         print("line " + str(line) + ": " + str(s[n]) + "->" + str(n))         n = s[n] - 1         line += 1