Learn to Code via Tutorials on Repl.it!

← Back to all posts
DP #1: Introduction to Dynamic Programming
h
MrEconomical (2194)

PREREQUISITES: BASIC UNDERSTANDING OF ALGORITHMS + UNDERSTANDING OF RECURSION

What is dynamic programming?

Many problems can be solved by breaking them down into smaller problems, then taking these smaller problems and constructing the final solution. Usually, the solutions for these problems are implemented recursively - a function calls itself to solve the smaller subproblems, then eventually combines these solutions to form the answer for the larger problem. Let's take a look at a very simple example of recursive calculation with the fibonacci sequence. No doubt as you already know, the fibonacci sequence is defined as f(n) = f(n - 1) + f(n - 2) with f(0) = 0 and f(1) = 1.

A simple recursive function to calculate the fibonacci sequence would look something like this:

function fib(n)
    if (n == 0 or n == 1)
        return 1
    else
        return fib(n - 1) + fib(n - 2)

The diagram below represents how this program would calculate the sequence:


Figure from https://www.researchgate.net/figure/Cilk-pseudocode-for-a-recursive-program-to-compute-Fibonacci-numbers-main_fig1_278965757

To calculate the 4th fibonacci number, the program would have to calculate the 3rd and the 2nd. However, to calculate the 3rd fibonacci number, the program calculates the 2nd again! As you can see, with a recursive implementation, our program performs many duplicate calculations which will affect its speed.

Dynamic programming is an optimization to recursion that removes all of the inefficiencies of duplicate calculations. Instead of starting at the highest level problem and requesting solutions to smaller problems, dynamic programming starts at the smallest level problem, and uses the solutions to those problems to build up to the top level solutions. This is known as a bottom-up construction versus the top-down construction of recursion.

What does dynamic programming look like?

Usually, dynamic programming is implemented iteratively with a table instead of recursively calling a function. The algorithm starts at the lowest levels of the problem, then iterates along and uses its previous solutions until it reaches the desired solution. A dynamic programming approach to calculate the fibonacci sequence would look something like this:

calculated = 0
x = 1
y = 1

while (calculated < desired)
    y = x + y
    x = y
    calculated ++

This is one of the most simple examples of dynamic programming. In fact, you probably have already written this exact program before! The fibonacci sequence is especially easy to understand since we only require the previous solutions and the solution before that, so we can use 2 variables. However, in more complex dynamic programming problems, we usually store our previous solutions in a table so we can access them whenever we want.

Advantages of Dynamic Programming

Much faster - A recursive function will often perform many repeat calculations which slows it down. Consider the fibonacci example: the recursive function will run in O(2^n) time, while the dynamic programming solution is much faster, only needing O(n) time.

Not dependent on call stack - Recursive calls happen on a stack, with each call being added onto the stack for each level of recursion. This can produce some problems especially for larger data sets as the size of stacks are limited, meaning any recursion that goes deeper than the maximum stack size will fail. Dynamic programming is not limited by this.

Disadvantages of Dynamic Programming

Uses more memory - In order to store our previously calculated solutions, we usually use a table which will require more memory than a recursive implementation. However, as we will see later on, dynamic programming can be memory optimized so its memory footprint is not as large. In addition, the speed advantage usually far outweighs the memory disadvantage making dynamic programming much better.

I hope you found my tutorial useful! Next tutorial in the series: https://repl.it/talk/learn/DP-2-Basic-Dynamic-Programming-Problems/32158

Commentshotnewtop
StudentFires (327)

Doesn't the data consumed in the multiple calls across the stacks usually outweigh the size of the table?

MrEconomical (2194)

@StudentFires what do you mean, data consumed?

StudentFires (327)

@MrEconomical Sorry, I meant data used at the current point in time. As the data can't be "consumed."

MrEconomical (2194)

@StudentFires well, by "uses more memory" I merely meant that keeping track of all the previous calculated values might be a bit memory intensive especially when data sets get extremely large and we might need to keep track of millions of previously calculated values

StudentFires (327)

@MrEconomical I thought about what happens when it's been called a lot of times, but "millions"!? Oh yeah, lol, the Fibonacci does that by the time you call f(50).

MrEconomical (2194)

@StudentFires which is why we need optimizations ;)

StudentFires (327)

@MrEconomical As long as you aren't sacrificing readability or something right? Unlike 100% of my code, since I truly began to understand code.

MrEconomical (2194)

@StudentFires by optimizations, I mean optimizations of the algorithm itself like discarding some unneeded parts of the array (unneeded old solutions) in the middle of our code running, not optimizations like making our code shorter. but that's all for a later tutorial not here

StudentFires (327)

@MrEconomical Sometimes, something can be long and hard to understand, while a shorter piece of code can be easier to understand. There isn't a direct correlation between length and readability.

MrEconomical (2194)

@StudentFires sometimes, and optimized piece of code can be extremely simple and easier to understand than an unoptimized algorithm. There isn't a direct correlation between optimization and readability.

DynamicSquid (1959)

I hate algorithms (and logic, and thinking in general), but I know that I should learn them. But I never do since all the tutorials out there are too complex. But this tutorial was actually really easy to understand Thanks!

AdCharity (1287)

You didn't give me any leaks >:(

MrEconomical (2194)

@AdCharity wrote it in 10 minutes, sorry!

AdCharity (1287)

@MrEconomical why does my cycle count look like binary

AdCharity (1287)

@MrEconomical you got me there
Edit: conspiracy

  • 13 also means D
  • D is the second letter in AdCharity
  • Two in binary is 0b10
  • My average grade is a B + 1 letter grade
  • B + 1 letter grade = A which is the 1st character of AdCharity!!!
    Coincidence? I think not.

Edit 3: that made no sense sorry

sugarfi (493)

@AdCharity what do you mean? 13 means \r

Roar123 (424)

Great explanation! You took a big concept and built it up in bite-sized easy to follow chunks (just like dynamic programming :)

KathySmith (0)

Thank you for creating this.

moshtica (0)

Thank You Mr.Econemical!
I have learned from your easy understanding tutorial.
I am waiting for the next Chapter

sugarfi (493)

Tail recursion is its own reward.