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

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
def min_cost(M, l):
    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)]
    best_k = [None for _ in range(n)]

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

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

    return total_cost[n-1], best_k


def _line_print(words, i, j):
    ret = words[i]
    for k in range(i+1,j):
        ret += " " + words[k]
    return ret

def pretty_print(words, best_k, j):
    if j==0:
        return words[0]
    k = best_k[j]
    ret = pretty_print(words, best_k, k)
    ret += "\n"
    ret += _line_print(words, k+1, j)
    return ret



# MAIN FUNCTION
print()
tc, best_k = min_cost(M, l)
print(tc)
print(pretty_print(words, best_k, len(l)-1))