Dynamic Programming - Καλαίσθητη εκτύπωση

text = """Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."""

# Initialization
M = 20
words = text.split(" ")
print(words)
# l = [len(word) for word in words]
l = list()
for i in range(len(words)):
    l.append(len(words[i]))
print(l)

# Problem
n = len(l)
extra = [[0 for _ in range(n)] for __ in range(n)]
line_cost = [[0 for _ in range(n)] for __ in range(n)]

# Η extra βρίσκει πόσο εξω βγαινω απο το οριο των Μ χαρακτηρων
# αν ψαξω απο την i στην j λεξη
for i in range(n):
    # Πρέπει να είναι πάντα l[i] < M, για να δουλέψει αυτό
    extra[i][i] = l[i] - M
    if extra[i][i] > 0:
        line_cost[i][i] = float('inf')
    else:
        line_cost[i][i] = extra[i][i]**2
    for j in range(i+1, n):
        # extra[i, j] = sum(l[k]+1 for k in range(i, j+1)) - M
        extra[i][j] = extra[i][j-1] + l[j] + 1
        if extra[i][j] > 0:
            line_cost[i][j] = float('inf')
        else:
            line_cost[i][j] = extra[i][j]**2     # Για να γίνει θετικό



# total_cost = [[None for _ in range(n)] for __ in range(n)]
'''
for i in range(n):
    for j in range(i):
        total_cost[i][j] = 0
    total_cost[i][i] = line_cost[i][i]
'''



# Ορίζω αλλιώς την μεταβλητή
# total_cost[0][j] = cost to go up to word j = total_cost[j]
# 1. Δέσμευση πίνακα
total_cost = [None for _ in range(n)]

# 2. Αρχικές τιμές
total_cost[0] = line_cost[0][0]

# 3. For-loops και σειρά προσπέλασης στοιχείων
for j in range(1, n):
    total_cost[j] = min(total_cost[k] + line_cost[k+1][j] for k in range(j))

print(total_cost[n-1])