What Is Dynamic Programming?

This article is for those who have heard about Dynamic Programming and for those who have not heard but want to know more about it. In this article, I will cover all those topics which can help you to work with DP.

Index:

1. Intro of Dynamic Programming
2. Must have properties for DP!!
3. Implementation of DP
4. Approach of solving a Dynamic Programming Problem
5. Its applications

Lets start discussing Dynamic Programming 🤓.

✒️ Intro of Dynamic Programming

So now the question arises, then What is a Dynamic Programming? In simple words,

'' Dynamic Programming is an optimized plane recursion, which solves problem in polynomial time (not in exponential as plane recursion does).''

Yes, Dynamic Programming is just an optimization over recursion. The idea 💡 behind Dynamic Programming is that, if there are some overlapping subproblems (will clear soon), then we can store results of them and reuse that result, if same subproblem needed again. By using this Idea, DP saves time and number of comparisons.

For those, who don't know what is a plane recursion?

Plane recursion is a way of solving problem. In which we break a big problem into smaller subproblems, and then we use result of subproblems for solving big problem.

✒️ Must have properties for DP!!

Before we discuss, that how Dynamic Programming does optimization over plain recursion? Let we first see, which type of problems can be solved by DP:

1. Problems with Overlapping Subproblems:

As we know, in recursion, we divide a problem into subproblems. And If there are some subproblems present, which we are computing again and again, then it is known as Overlapping Subproblems. In Dynamic Programming, we store the result of subproblem at a place (we will see how?), and uses that result instead of calculating again, whenever we need. In this way, we save our valuable time. 😀

For example : If we take an example of finding nth Fibonacci number, then for 5th Fibonacci number, we computes 3rd Fibonacci 2 times, and 2nd Fibonacci 3 times.

So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point in storing the solutions if they are not needed again.

As recursion also used in many Divide and Conquer algorithms but we can not use Dynamic Programming there, because those algorithms do not have overlapping subproblems.

2. Existence of Optimal Substructure:

a problem can have Optimal Substructure, if its optimal solution can be calculated from optimal solutions of its subproblems.

Like for Fibonacci number, Optimal Substructure is

fib(n) = fib(n-1) + fib(n-2)

💡 If you find any problem with these two properties, then that problem can be solved by Dynamic Programming.

✒️ Implementation of DP

Under this topic, we will see now that how Dynamic Programming does optimization over plain recursion ?

1. Implementation using Top - Down Approach:

This approach is very similar to Recursion, with only some modifications. In this we store the result of subproblems in a memo array (or you can use any other structure). Because if we need them again, we can find their values in memo array.

/*
    c++

    optimization of fibonacci numbers implementation
    time comlexity : O(n) rather than exponential ,as in older recursive implementation.
*/
int fib(int n, int memo[])
{
    if (memo[n] == -1) // if we encounter this number first number, as memo[] is initialized with -1
    {
        int res;
        if (n == 0 || n == 1)
        {
            res = n;
        }
        else
        {
            res = fib(n - 1, memo) + fib(n - 2, memo);
        }
        memo[n] = res;
    }
    return memo[n];
}

By using this approach, for finding 5th Fibonacci number, 3rd Fibonacci will be calculated only 1 time, and next time we will get its value from memo array. Same happens for 2nd Fibonacci.

This approach is knowns as Top-Down, because in this we are starting from main problem (top in recursion) and then we are breaking it into subproblems and storing results of its subproblems. This is also known as Memoization .

2. Implementation using Bottom - Up Approach:

This approach of implementation is opposite of Top-Down approach, because in this, we do not use recursion. In this approach, we start solving subproblems first (bottom up manner), and storing their results in a table ( an array). And in last we calculate the Top problem, using results in table.

For nth Fibonacci number, Bottom-Up approach can be implemented as:

// c++
int fib(int n)
{
    int table[n + 1];
    table[0] = 0, table[1] = 1;
    for (int i = 2; i <= n; i++)
        table[i] = table[i - 1] + table[i - 2];
    return table[n];
}

Why we used one dimensional array? Dimension of array depends on number of variables we are changing in recursive implementation. If you know recursive implementation of nth Fibonacci number, then you can see that we only change one parameter for every recursive call. That's why we used only one dimensional array.

💡 In many problems, we use more than one dimensional array. for better understanding, you may have a look at my repo (link given in the end*).

This approach is also known as Tabulation. As we fill a table in this.

Dynamic Programming does optimization over plain recursion, by changing implementation approach for the problem.

✒️ Approach of solving a Dynamic Programming Problem

Now we have reached on second last topic of this article, 😎. Let we discuss, what should be our approach for solving Dynamic Programming Problem.

As Dynamic Programming solutions are faster than exponential brute method, So we should try to think Dynamically for a problem.

1. Identify DP: the first approach for solving a Dynamic Programming Problem, is that we should first identify that the given problem can be solved by Dynamic Programming or not.

And how we can identify this? by looking for "must have properties for DP" in the given problem.

2. Decide parameters: second step for solving a Dynamic Programming Problem is, decide which are the parameters with which we will deal, to solve the problem.

As in Fibonacci number, it is the parameter

n

3. Relate parameters with subproblem : the third step for solving a Dynamic Programming should be, try to relate the parameter (which we decided in step 2) with different problems.

As for 7th Fibonacci number,

n = 7

fib(n=7) = fib(n=6) + fib(n=5)

Basically, try to build optimal substructure.

4. Code for the problem : now the last step, write code for the problem. Either by using top-down approach or bottom-up approach.

✒️ Its applications

From computer science perspective, Dynamic Programming has many applications. Because there are many problems present, whose solutions are based on DP. Some of its applications includes:

• Diff Utility (based on Longest Common Subsequence problem*): This is used to find difference between two files, used in Git also.
• Resource Allocation (based on 0-1 knapsack problem*)
• ️Search Closed Words (based on Edit Distance problem*)
• Floyd war shall algorithm: In this, we find shortest distance between every pair of vertex in graph.
• Bellman Ford algorithm: used to find shortest distance between source router and destination router.

Reach The End!