Dynamic Programming, Part 1

Introduction

This is a note I took while taking Avik Das’ Dynamic Programming course at Linkedin Learning. His course is awesome and I highly recommend it!

What is Dynamic Programming?

The technique for computing a recursive algorithm with highly overlapping subproblems by only solving each subproblem once.

Left - Recursive Programming, Right - Dynamic Programming

Fibonacci sequence problem

Memoization

A technique for speeding up computations by caching results of repeated calculations.

Memoization

Fibonacci using memoization

Python example

As you can see, memorization uses more space. To reduce space usage, we can use a bottom-up dynamic programming approach.

Bottom-up Dynamic Programming

All DAGs are linearizable.

we can remove vertice as we continue next vertice

#include <iostream>
using namespace std;
int n = 0;
int fib(int n)
{
    if (n==0) return 0;
    if (n==1) return 1;
    int a = 0;
    int b = 1;
    int temp = 0;
    for (int i=2; i<=n; i++) {
        temp = a;
        a = b;
        b = temp + b;
    }
    return b;
}
int main()
{
    cin >> n;
    cout << fib(n-1) << endl;
    return 0;
}