Poda
Lição 11 de 15 do curso Programação Dinâmica 101 da Coddy.
A poda é uma técnica utilizada para reduzir o número de computações exigidas por um algoritmo de programação dinâmica, evitando computações desnecessárias. Isso é feito eliminando certos ramos da árvore recursiva que não levarão a uma solução melhor do que a melhor solução encontrada até agora. A poda pode ser usada tanto em algoritmos de programação dinâmica top-down quanto bottom-up.
Desafio
EspecialistaNeste desafio, você recebe uma matriz de inteiros e um valor alvo. Sua tarefa é escolher um número inteiro de cada linha da matriz, de modo que a diferença absoluta entre o valor alvo e a soma dos inteiros escolhidos seja minimizada. Você deve então retornar o valor desta diferença absoluta mínima.
Experimente você mesmo
def minimize_difference(mat, target):
# Escreva o código aquiTodas as lições de Programação Dinâmica 101
1Introdução à Programação Dinâmica
O que é programação dinâmica?Por que ela é importante?Aplicações em diversas áreas3Algoritmos de programação dinâmica
Maior subsequência comumProblema da mochilaProblema do trocoDistância de edição