Dynamic Programming Problems

I have always liked dynamic programming. I went on a kick recently where I wrote solutions to several classic dynamic programming problems.

GeeksforGeeks published my implementation of the weighed interval scheduling problem. I wrote a Python program and a Java program to solve the weighted interval scheduling problem. When I was researching the problem, I noticed that the solution on GeeksforGeeks ran in O(n ^ 2) time, but I knew that the problem can be solved in O(n log n) time. So, I submitted a modification, and GeeksforGeeks accepted it.

Here are my implementations of several solutions to the discrete knapsack problem. I wrote a naive recursive solution, a memoized recursive solution, and a bottom-up dynamic programming solution.

I also implemented a naive recursive solution, a memoized recursive solution, and a bottom-up dynamic programming solution for the longest common subsequence problem.

Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, shows the optimal way to cut up a rod whose pieces you want to sell, and I implemented their solution in Python.

I implemented a bottom-up dynamic programming solution to the longest increasing subsequence problem.

Here are my implementations of the Fibonacci sequence. Again I wrote a naive recursive solution, a memoized recursive solution, and a bottom-up dynamic programming solution.

Here are my implementations of combination. I wrote a naive recursive solution, a memoized recursive solution, and a bottom-up dynamic programming solution.

Further resources:

Bellman, Richard. Dynamic Programming. Princeton, NJ: Princeton University Press, 1957.

http://cs.stackexchange.com/questions/28111/proof-of-an-optimal-substructure-in-dynammic-programming/28114#28114

http://programmers.stackexchange.com/questions/140233/how-to-prove-a-dynamic-programming-strategy-will-work-for-an-algorithm

https://www.cs.oberlin.edu/~asharp/cs280/2012fa/handouts/dp.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s