Estou tentando entender o conceito de programação dinâmica, através do curso MIT OCWAqui. A explicação sobre o vídeo do OCW é ótima e tudo mais, mas sinto que não entendo até que implementei a explicação no código. Ao implementar, refiro-me a algumas notas da nota de aulaAqui, particularmente a página 3 da nota.

O problema é que não tenho ideia de como traduzir parte da notação matemática para código. Aqui está uma parte da solução que implementei (e acho que está implementada corretamente):

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 > page_width:
        return float('nan') 
    else:
        return math.pow(page_width - line_len, 3)

Agora a parte que não entendo está no ponto 3 a 5 nas notas da aula. Eu literalmente não entendo e não sei por onde começar a implementá-las. Até agora, tentei iterar a lista de palavras e contar a maldade de cada final de linha, assim:

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?

Mas então, não sei como posso continuar a função e, para ser sincero, não entendo essa linha:

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

e como vou voltarjustifier como umint (desde que eu já decidi armazenar o valor de retorno emresult, que é uma lista. Devo fazer outra função e reciclar de lá? Deveria haver alguma recursão?

Poderia, por favor, me mostrar o que fazer a seguir e explicar como isso é programação dinâmica? Eu realmente não consigo ver onde está a recursão e qual é o subproblema.

Obrigado antes.