Dynamic Programming
Dynamic Programming is another Divide and Conquer method of solving problems. Similar to recursion, we make make use of smaller cases of the problem to solve larger cases. The difference is that in recursion, we store the solutions to the smaller cases to avoid recomputing them. At times, DP (the street name for Dynamic Programming) is significantly more efficient than recursive solutions to the same problem. Here is a problem that runs significantly faster when using DP than when using recursion:
Example:
Let us have a rod of length n. We can divide this rod into smaller rods of integer lengths. Each length of a rod sells at a given price. What is the maximum revenue we can have by dividing this rod?
Prices:
Length 1 2 3 4 5 6 7 8 9 10
Price $3 $7 $9 $12 $15 $19 $21 $24 $28 $30
Solution Using Recursion:
def cut_rod(n, p):
"""
Recursive Solution to the rod cutting problem
"""
if n == 0:
return 0
return max((p[i] + cut_rod(n-i-1, p)) for i in range(n))
if __name__ == '__main__':
p = [3, 7, 9, 12, 15, 19, 21, 24, 28, 30]
print(cut_rod(10, p))
After running, this codes prints out the number 35 as the maximum revenue that we can by dividing a rod of length 10. Playing around with different, we can see that indeed this is true.
10 = 2 + 2 + 2 + 2 + 2
Maximum Revenue = $7 + $7 + $7 + $7 + $7 = $35
Solution Using Dynamic Programming:
def cut_rod(n, p, r):
"""
Dynamic Programming Solution to the rod cutting problem
"""
if n == 0:
return 0
elif r[n-1] != -1:
return r[n-1]
r[n-1] = max((p[n-1-i] + cut_rod(i, p, r)) for i in range(n))
return r[n-1]
if __name__ == '__main__':
p = [3, 7, 9, 12, 15, 19, 21, 24, 28, 30]
r = [-1 for x in range(10)]
print(cut_rod(10, p, r))
This solution produces the same output as the recursion solution, 35. The difference here is that instead of simply calling the recursion function to solve for our smaller cases, we check if it has already been solved and use the answer it if it has been.
Runtime Analysis:
By going through the code for the first method and analyzing its recursion tree, we can see that it has a runtime of order O(2^n). Analyzing the runtime of the second solution tells us that its runtime is of order O(n^2) which is significantly smaller!!!!!
Sample Runtimes:
Case 1 5 10 15 20 25
Recursion 0.001 0.001 0.002 0.036 1.334 42.684
Dynamic Programming 0.001 0.001 0.001 0.001 0.001 0.001
You are way ahead of what they teach you! If you liked what you did here with dynamic programming, you will certainly like the problem of generating longest common substring (LCS) - http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
ReplyDeleteIt's almost 3 am right now and I'm trying to write an essay that is due at 10 am. I took a break in the middle and looked at the link. It was a very interesting read. Thank you for the link!
DeleteThis was a fascinating blog post! It's really impressive how simply avoiding resolving subproblems leads to such a dramatic increase in efficiency. Last week we looked at memoization, which from what I gather avoids resolving subproblems like dynamic programming but still uses recursion. I was wondering how memoization compares with dynamic programming in terms of efficiency when used to solve different problems. I wish we spent more time studying these different techniques in class, but I guess there's only so much that can be packed into a semester-long course.
ReplyDeleteAlso, if you're interested here's a link to my blog:
Deletehttp://mttsslog.blogspot.ca
I also wish we had spent more time on such topics in class. It would've been a quite interesting topic.
DeleteAs for the difference between memoization and dynamic programming, all I can think of is the following:
- Similar to recursion, memoization has a top-down approach whereas dynamic programming has a bottom-up approach
- Also, as Danny mentioned, you can write a piece of code to turn a recursive function into a memoized function. But you cannot turn a recursive solution to a dynamic programming solution using a set function.
P.S. I enjoyed your blog post regarding assignment 2 and regular expressions.