DP #1: Introduction to Dynamic Programming
h
MrEconomical (2195)

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

You are viewing a single comment. View All
sugarfi (493)

Tail recursion is its own reward.