Tutorial For Dynamic Programming Begginer to Advance

1. Introduction
2. Recursion and Dynamic Programming
3. Some examples with solution

Introduction

Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.

There are two ways of doing this.

1.) Top-Down :

Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.

2.) Bottom-Up :

Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.

Fibbonaci Series :

Let's try to understand this by taking an example of Fibonacci numbers.

Fibonacci (n) = 1; if n = 0
Fibonacci (n) = 1; if n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

So, the first few numbers in this series will be: 1, 1, 2, 3, 5, 8, 13, 21... and so on!

A code for it using pure recursion:

Recursion Solution

    int fib (int n) {
        if (n < 2)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }

Using Dynamic Programming approach with memoization:

    void fib () {
        fib_result[0] = 1;
        fib_result[1] = 1;
        for (int i = 2; i < n; ++i)
           fib_result[i] = fib_result[i - 1] + fib_result[i - 2];
    }

Nth Fibonacci number

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

Fibonacci numbers occur in the sums of "shallow" diagonals in Pascal's triangle !

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

Related Problems:

1. Fun With Fibonacci devskill
2. DZY Loves Fibonacci Numbers, codeforces, codeforces
3. Weasel does Xor on Tree, codeforces
4. Longest Common Subsequence, codechef
5. Longest Increasing Subsequence, codeforces
6. LCIS, codeforces
7. LCS Again, codeforces
8. Gargari and Permutations, codeforces
9. Beautiful Sequence, hackerearth
10. CODEM2 - Problem2, spoj
11. CODEM3 - Problem3, spoj
12. CODEM4 - Problem4, spoj
13. CODEM5 - Problem5, spoj
14. BAT3 - BATMAN3, spoj
15. BAT4 - BATMAN4, spoj
16. AEROLITE - The Secret of an Aerolite, spoj
17. AIRLINES - Jumbo Airlines, spoj
18. ALWFACT - Allowed Factors