Dynamic Programming: The Basics

-

What is dynamic programming?

Use this algorithmic strategy to solve a problem by remembering its subproblems so you don't have to solve them more than once! It's a concept that I think is best understood by applying it to examples. The classic example is calculating Fibonacci numbers. 

A naive approach to calculating Fibonacci numbers

Maybe the most straightforward method to calculate Fibonacci numbers is as follows: 

 public static int method1(int n) {
if(n <= 2) return 1; 
else return method1(n-1) + method1(n-2); 

}

 However, this method is slow: if T(n) is the amount of time it takes, then T(n) = T(n-1)+T(n-2) + O(1) because we add the amount of time it takes to calculate each subproblem as well as some constant time for comparisons, etc. Then T(n) = T(n-1) + T(n-2) + O(1) > 2T(n-2) + O(1) > 2^(n-2).  Thus, this method takes exponential time! 

 Why is this method so slow? If we look at the tree of subproblems that we're calculating, we see that we are calculating the same subproblems over and over again! 
Fibonacci tree with color coded subproblems
How can we do better?

Memoization (top down)

One type of dynamic programming is called memoization. This top down approach is pretty simple...
Using this approach to solve our Fibonacci example, we don't have to calculate the same subproblem more than once, so our tree becomes a lot smaller!  
Written in code, this solution looks like...

static int[] memo; 

public static int method2(int n) {
if(memo[n] != -1) return memo[n]; 
else {
if(n <= 2) return 1; 
else {
memo[n] = method2(n-1) + method2(n-2); 
return memo[n]; 
}
}
}

This method is a lot faster! Since there are n non-memoized calls, and each one takes a constant amount of time, the overall time is linear. 

Tabulation (bottom up)

Another type of dynamic programming is tabulation. This bottom up approach is perhaps even more straightforward than memoization, because we build up from the base cases until we calculate our final answer. Here is the code:

static int[] tab; 
public static int method3(int n) {
for(int i = 1; i <= n; i++) {
if(i <= 2) tab[i] = 1; 
else tab[i] = tab[i-1] + tab[i-2]; 
}
return tab[n]; 
}

We can actually do better and save space if we only record the previous two values instead of all the previous values... 

public static int better_method3(int n) {
if(n <= 2) return 1; 

int prev = 1, curr = 1, next; 
for(int i = 3; i <= n; i++) {
next = prev + curr;
prev = curr;
curr = next; 
}

return curr; 
}

Putting it together

If we time all the methods, we can see the power of dynamic programming. If we want to calculate the 50th Fibonacci number, the naive approach took around 37.97 seconds. All the other approaches took much less than that - around 0.000016133, 0.000008461, and 0.000005634 seconds! (I got these numbers by running each of the methods 5 times, and taking the average.)

All code on my Github - try running it yourself! 

 Source(s): MIT OCW

Popular posts from this blog

Building A Toy Language Interpreter in Go

-
Image
In this post, I'll be giving a high-level overview of interpreters, why they're interesting, and how they work. I'll be referencing my repo, go_interpreter , which is a simple interpreter written in Go for a toy language. The figure below shows the structure of our interpreter with an example input: What is an interpreter?  An interpreter is a language processor that seems to directly execute the source program on user input: In contrast, a compiler first takes in a source program and translates it to an executable machine code target program. Then, the user can pass in inputs to this target program and get outputs. In general, an interpreter is better at reporting errors since it's processing statements one at a time, and a compiler is faster at generating outputs from inputs. In this post, we're going to go over a simple interpreter that is capable of supporting: integers, booleans, strings, arrays, hashmaps prefix, infix operators index opera
Read more

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each instance of a type that impleme
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized
Read more