Resolução do problema cortes de hastes com programação dinâmica

cut_rod_pd.py

def cut_rod_pd(p, n):
    memory = {}
    memory[0] = 0
    memory[1] = p[1]
    for i in range(2, n + 1):
        best_choice = p[i]
        for j in range(1, i // 2 + 1):
            # print(f"Haste tamanho {i}, combinação {i - j}-{j}")
            choice = memory[i - j] + memory[j]
            if choice > best_choice:
                best_choice = choice
        memory[i] = best_choice
    return memory[n]