Pruning
Lesson 11 of 15 in Coddy's Dynamic Programming 101 course.
Pruning is a technique used to reduce the number of computations required by a dynamic programming algorithm by avoiding unnecessary computations. This is done by eliminating certain branches of the recursive tree that will not lead to a better solution than the best solution found so far. Pruning can be used in both top-down and bottom-up dynamic programming algorithms.
Challenge
ExpertIn this challenge, you are given a matrix of integers and a target value. Your task is to choose one integer from each row of the matrix, such that the absolute difference between the target value and the sum of the chosen integers is minimized. You must then return the value of this minimum absolute difference.
Try it yourself
def minimize_difference(mat, target):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance