I just realized I do not make much use of this blog. It is my "blog" on codeforces, not a forum. So I can write whatever I feel like (keeping it as close to programming as possible). ;)
I have been reading about Dynamic Programming (DP) lately. I think I've finally got the gist of it. DP isn't an algorithm that you can apply to a certain types of problems. It is essentially just a technique, an optimization technique to be exact. And it can be applied to problems having the following two properties:
- Optimal Substructure: What this means is that the solution to larger problem, depends on similar smaller problems. This is essentially the same as a divide and conquer technique, where we divide the problem into smaller sub problems, and solve those to get solution to our bigger problem. But, there is a significant difference between DP and divide and conquer problems, which is...
- Overlapping Subproblems: Unlike divide and conquer, DP is applied to problems where sub problems are solved more then once. For example the recursive (which is essentially divide and conquer) solution to merge sort problem divides an array into two distinct arrays, and sorts them independently to get an overall solution. Thus you can't apply DP in this case. But in cases where a certain subproblem might appear more times than once, DP is the way to go. An example of this is the fibonacci series, where to get a certain number in fib series, you have to solve the same sub problem more then once.
When a problem exhibits the above two properties, you can apply DP. Meaning, keep record of subproblems solved, so that the next time you solve a subproblem, you first look it up and see if it has already been solved, avoiding solving it again. Or you can follow a bottom up approach, solving the smaller problems first, before solving the larger problem, iteratively.This can reduce an exponential complexity algorithm to polynomial complexity one.
While it is easy to get the gist of DP, it isn't always that easy to apply in competition, and requires a lot of practice. For example in the recent SRM (520) on Topcoder, I was able to identify that the hard problem in DIV-2 (medium in DIV-1) was a DP problem, but I wasn't able to come up with a proper recursion.
Looking forward to solving a good number of DP problems in coming days...
Cheers!
Comments (0)
