Quy trình lập trình · Ngắt dòng với độ lệch nhỏ nhất

def wrap_words(words, width):
    words = tuple(words)
    if type(width) is not int or not 1 <= width <= 80 or len(words) > 100:
        raise ValueError("wrap.limit")
    if any(type(w) is not str or not w or len(w) > width or any(c.isspace() for c in w) for w in words):
        raise ValueError("wrap.word")
    n = len(words)
    costs, ends = [0] * (n+1), [0] * n
    for i in range(n-1, -1, -1):
        used, best = 0, None
        for j in range(i, n):
            used += len(words[j]) + (j > i)
            if used > width:
                break
            cost = 0 if j == n-1 else (width-used)**2 + costs[j+1]
            if best is None or cost < best:
                best, ends[i] = cost, j+1
        costs[i] = best
    lines, i = [], 0
    while i < n:
        lines.append(" ".join(words[i:ends[i]]))
        i = ends[i]
    return lines