Staram się zrozumieć koncepcję programowania dynamicznego poprzez kurs na temat MIT OCWtutaj. Wyjaśnienie na temat wideo OCW jest wspaniałe, ale czuję, że tak naprawdę nie rozumiem go, dopóki nie zastosuję wyjaśnienia w kodzie. Podczas implementacji odsyłam do notatek z notatki z wykładututaj, szczególnie strona 3 notatki.

Problem polega na tym, że nie mam pojęcia, jak przetłumaczyć niektóre zapisy matematyczne na kod. Oto część rozwiązania, które zaimplementowałem (i myślę, że zostało ono zaimplementowane poprawnie):

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)

Teraz część, której nie rozumiem, znajduje się w punkcie 3 do 5 w notatkach z wykładu. Dosłownie nie rozumiem i nie wiem, od czego zacząć ich wdrażanie. Do tej pory próbowałem powtórzyć listę słów i policzyć zło każdego rzekomo końca linii, jak poniżej:

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?

Ale nie wiem, jak mogę kontynuować tę funkcję i szczerze mówiąc, nie rozumiem tej linii:

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

i jak wrócęjustifier jakoint (odkąd zdecydowałem się przechowywać wartość zwracaną wresult, która jest listą. Czy powinienem zrobić inną funkcję i stamtąd powtarzać? Czy powinna być jakakolwiek rekursja?

Czy mógłbyś mi pokazać, co robić dalej i wyjaśnić, jak to jest programowanie dynamiczne? Naprawdę nie widzę, gdzie jest rekursja i czym jest problem.

Dzięki wcześniej.