title: Implementing Text Justification with Dynamic Programming
body: <p>I'm trying to understand the concept of Dynamic Programming, via the course on MIT OCW <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/#vid_playlist">here</a>. The explanation on OCW video is great and all, but I feel like I don't really understand it until I implemented the explanation into code. While implementiing, I refer to some notes from the lecture note <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec20_orig.pdf">here</a>, particularly page 3 of the note.</p>
  
  <p>The problem is, I have no idea how to translate some of the mathematical notation to code. Here's some part of the solution I've implemented (and think it's implemented right):</p>
  
  <pre><code>import math
  
  paragraph = "Some long lorem ipsum text."
  words = paragraph.split(" ")
  
  # Count total length for all strings in a list of strings.
  # This function will be used by the badness function below.
  def total_length(str_arr):
      total = 0
  
      for string in str_arr:
          total = total + len(string)
  
      total = total + len(str_arr) # spaces
      return total
  
  # Calculate the badness score for a word.
  # str_arr is assumed be send as word[i:j] as in the notes
  # we don't make i and j as argument since it will require
  # global vars then.
  def badness(str_arr, page_width):
      line_len = total_length(str_arr)
      if line_len &gt; page_width:
          return float('nan') 
      else:
          return math.pow(page_width - line_len, 3)
  </code></pre>
  
  <p>Now the part I don't understand is on point 3 to 5 in the lecture notes. I literally don't understand and don't know where to start implementing those. So far, I've tried iterating the list of words, and counting the badness of each allegedly end of line, like this:</p>
  
  <pre><code>def justifier(str_arr, page_width):
      paragraph = str_arr
      par_len = len(paragraph)
      result = [] # stores each line as list of strings
      for i in range(0, par_len):
          if i == (par_len - 1):
              result.append(paragraph)
          else:
              dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)] 
              # Should I do a min(dag), get the index, and declares it as end of line?
  </code></pre>
  
  <p>But then, I don't know how I can continue the function, and to be honest, I don't understand this line:</p>
  
  <pre><code>dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)] 
  </code></pre>
  
  <p>and how I'll return <code>justifier</code> as an <code>int</code> (since I already decided to store return value in <code>result</code>, which is a list. Should I make another function and recurse from there? Should there be any recursion at all?</p>
  
  <p><strong>Could you please show me what to do next, and explain how this is dynamic programming?</strong> I really can't see where the recursion is, and what the subproblem is.</p>
  
  <p>Thanks before.</p>