Ich versuche, das Konzept der dynamischen Programmierung anhand des Kurses über MIT OCW zu verstehenHier. Die Erklärung zu OCW-Video ist großartig, aber ich habe das Gefühl, dass ich es nicht wirklich verstehe, bis ich die Erklärung in Code implementiert habe. Während der Implementierung verweise ich auf einige Notizen aus dem SkriptHier, insbesondere Seite 3 des Vermerks.

Das Problem ist, ich habe keine Ahnung, wie man einen Teil der mathematischen Notation in Code übersetzt. Hier ist ein Teil der Lösung, die ich implementiert habe (und die ich für richtig halte):

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)

Jetzt ist der Teil, den ich nicht verstehe, auf den Punkten 3 bis 5 im Skript. Ich verstehe das buchstäblich nicht und weiß auch nicht, wo ich damit anfangen soll. Bisher habe ich versucht, die Liste der Wörter zu durchlaufen und die Schlechtigkeit jedes angeblichen Zeilenendes wie folgt zu zählen:

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?

Aber dann weiß ich nicht, wie ich die Funktion fortsetzen kann, und um ehrlich zu sein, verstehe ich diese Zeile nicht:

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

und wie ich wiederkommejustifier als einint (da ich mich bereits entschieden habe, den Rückgabewert in zu speichern)result, das ist eine Liste. Soll ich eine andere Funktion übernehmen und von dort zurückgreifen? Sollte es überhaupt eine Rekursion geben?

Könnten Sie mir bitte zeigen, was als nächstes zu tun ist, und erklären, wie dies dynamische Programmierung ist? Ich kann wirklich nicht sehen, wo die Rekursion ist und was das Unterproblem ist.

Danke schon mal.