Why should I care about dynamic programming? Dynamic programming is the process of breaking down a larger problem into smaller problems. By using the answers to those smaller problems, we can find the overall solution more efficiently. We'll also learn about the term 'memoization', and how it relates to dynamic programming. How does dynamic programming work? The usual example of dynamic programming is the Fibonacci Sequence. It's a good example, so we'll use it here too. If you're already familiar with the Fibonacci Sequence (and calculating it using recursion), then feel free to skip this next section. If you're not sure what that means, or you want a quick refresher, read on... The Fibonacci Sequence This is a sequence of numbers, where each number is calculated by adding the previous two together: Imagine I ask you to programmatically calculate the 6th number in the sequence (which is , as shown above). 8 How would you calculate it? Here's some JavaScript code for a function that does just that: function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
        return 1;

    // Calculate the previous two values in the sequence
    // using this same function
    return f(n - 1) + f(n - 2)
}

// Calculate the 6th value in the sequence
let answer = f(6) This will work fine, but it's slow. You can see that the function calls itself; it is . recursive To calculate the 6th Fibonacci number, we first need to calculate the 4th and 5th Fibonacci numbers. Each of then have to calculate previous numbers, and this repeats all the way down to the beginning of the sequence. those their Here's what that looks like if we draw it out as a graph. You can see that there's a lot of duplication here. For example, the 2nd value in the sequence is calculated 5 times! For small numbers in the sequence, this isn't too bad, but it quickly gets worse. For later numbers in the sequence, this would soon become impractical, even on a modern computer. So how do we do better? Dynamic programming and memoization One way we could improve this function is to store the results of our previous calculations as we go along. That way, we only need to calculate each number in the Fibonacci sequence once. This is the essence of dynamic programming: Dynamic programming is breaking the problem into problems, and using to get to the answer. larger smaller those Because we're achieving this by storing the previous results for later, we're also using 'Memoization': Memoization is storing the result of a previous calculation so that we can use it later, to make the overall algorithm more efficient. We could implement these concepts on the recursive approach above, but it's easier to follow if we use a 'bottom up' approach. Let's look at the code first, and then we can discuss why this is called a 'bottom up' algorithm: function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
        return 1

    let result = 0

    // Used to store the previous two results
    let lastButOneValue = 1
    let lastValue = 1

    // Work from item 3 of the sequence (items 1 and 2 are a 
    // special case, see above), calculate each value in turn
    for (let i = 3; i <= n; i++) {
        // Calculate this number by adding together the 
        // previous two
        result = lastValue + lastButOneValue

        // Update the values of the 
        // previous two items in the sequence
        lastButOneValue = lastValue
        lastValue = result
    }

    return result
}

// Calculate the 6th value in the sequence
let answer = f(6) Here, we calculate the Fibonacci sequence in order - all the way from the beginning - until we get to the number in the sequence that we need. As we go along, we store the results of the previous value, and the one before that. Getting the next value is then trivial.. just add those two together. Here's the graph from the original (inefficient) algorithm again, but we've highlighted only the calculations we're making in this new version: You can see that this time, rather than starting from the answer and working backwards, we work until we reach the value we need. forwards When we visualise it, we're working from the bottom of the graph upwards - hence a 'bottom up' approach. This algorithm is more efficient, there's no duplication at all! much We learned some new terms here, so let's recap: Recap: What is dynamic programming? Our latest algorithm uses . , because we're breaking the problem into problems, and using their results to get to the overall answer dynamic programming bigger smaller It also uses . , because we're storing the results of the previous step to avoid re-calculating them again later memoization It was a (rather than top-down, as in the less efficient algorithm). 'bottom up' approach because when we visualize the problem as a graph, we're working from the base of the graph upwards (also sent to the ) BaseClass newsletter

What Is Dynamic Programming and Memoization?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

13 Ways to Traverse a Tree: Recursion vs Iteration

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

13 Ways to Traverse a Tree: Recursion vs Iteration

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps