Can’t we make DP simpler ?
Dynamic Programming is one of the trickiest topic to learn and understand when people are starting with programming .
Lets see where we can apply DP .To apply DP to a problem we have to take care some of the points.We have to first see whether the problem contains two basic property to be solved using DP.
- Overlapping Sub problem property
- Optimal Sub Structure Property
Let’s understand one by one what we mean by it .
Overlapping Sub problem property
Here we decide whether the two sub problems are overlapping with the other sub problems or not .If they are not overlapping we can’t use DP , and that case is simply Divide and Conquer .To understand this better we look it recursive fibonacci problem .Suppose we want to find Fibonacci(4) ,so the recursive calls can be visualised like this
So as we see the recursive tree we can see there are various overallaping subproblem ,so in DP after calculating for once we dont calculate the sub problem again .
Optimal Sub Structure property
Here we decide whether we can break the problem in into optimal sub problems or not and then finding the solution of the problem.Optimal here have meaning as finding max ,min ,greatest and smallest .Let us look through a example . Suppose if we want to find out Fibonacci(4) ,then it can be broken into Fibonacci(3) + Fibonacci(2) .Easiest way to imagine this is to think whether any recursive solution exist for the problem or not .
To be Specific about what all problems can be solved using DP and its variation , we can categorise them as follows
- 0 -1 KnapSack Problem
- Unbounded KnapSack Problem
- Longest Common Subsequence Problem
- Longest Increasing Subsequence Problem
- Matrix Chain Multiplication Problem
- DP on Trees
- DP on Graph
- And Other Variations of DP
How DP is different from Divide and Conquer problems ?
In DP we have overlapping subproblems but in Divide and Conquer each and every solution is different and they don’t overlap with each other.
So how to solve any problem satisfying conditions of DP then ?
There are basically two approaches we can go .
- Top Down Approach
- Bottom Up Approach
Keep reading ,we will cover the above two approach in next post . Stay tuned .
Follow below link to move on to next.
