Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
120
votes
14answers
9k views
Throwing cats out of windows
Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can ...
40
votes
6answers
8k views
What is dynamic programming?
This is a really general question. What is dynamic programming (how's it different from recursion, memoization, etc)? I've read the wikipedia article on it but I still don't really understand it.
...
33
votes
9answers
14k views
Sum of digits of a factorial
Link to the original problem
It's not a homework question. I just thought that someone might know a real solution to this problem.
I was on a programming contest back in 2004, and there was this ...
31
votes
8answers
3k views
Find the number of occurrences of a subsequence in a string
For example, let the string be the first 10 digits of pi, 3141592653, and the subsequence be 123. Note that the sequence occurs twice:
3141592653
1 2 3
1 2 3
This was an interview ...
29
votes
8answers
16k views
Getting the submatrix with maximum sum?
Input: A 2-dimensional array NxN - Matrix - with positive and negative elements.Output: A submatrix of any size such that its summation is the maximum among all possible submatrices.
Requirement: ...
27
votes
7answers
1k views
Suggested algorithms/methods for laying out labels on an image
Given an image and a set of labels attached to particular points on the image, I'm looking for an algorithm to lay out the labels to the sides of the image with certain constraints (roughly same ...
25
votes
1answer
16k views
How to determine the longest increasing subsequence using dynamic programming?
Let's say I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming. This is simply out of practice, reviewing my old notes from my algorithms ...
24
votes
3answers
3k views
FSharp runs my algorithm slower than Python!
Years ago, I solved a problem via dynamic programming:
http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html
The solution was coded in Python.
As part of expanding my horizons, I recently started ...
23
votes
6answers
2k views
Challenging dynamic programming problem
This is a toned down version of a computer vision problem I need to solve. Suppose you are given parameters n,q and have to count the number of ways of assigning integers 0..(q-1) to elements of ...
22
votes
5answers
7k views
Dynamic programming - Largest square block
I need to find the largest square of 1's in a giant file full of 1's and 0's. I know i have to use dynamic programming. I am storing it in a 2D array. Any help with the algorithm to find the largest ...
22
votes
5answers
664 views
Algorithm for finding the busiest period?
I have some data like this:
1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15
I will attempt a representation to make it clearer:
1 2 3 4 5 6 7 ...
22
votes
4answers
12k views
A simple example for someone who wants to understand Dynamic Programming
I am looking for a manageably understandable example for someone who wants to learn Dynamic Programming. There are nice answers here about what is dynamic programming. The fibonacci sequence is a ...
19
votes
2answers
3k views
Which algorithms are hard to implement in functional languages?
I'm dabbling in functional languages and I have found some algorithms (especially those that use dynamic programming) harder to write and sometimes less efficient in worst case runtime. Is there a ...
18
votes
5answers
2k views
How are Dynamic Programming algorithms implemented in idiomatic Haskell?
Haskell and other functional programming languages are built around the premise of not maintaining state. I'm still new to how functional programming works and concepts in it, so I was wondering if ...
18
votes
2answers
2k views
What is difference between memoization and dynamic programming?
I think dynamic programming is subset of memoization. Is it right?
