Dynamic Programming resources in C?

Question

I'll be writing the online Google test tomorrow as a fresher. Apparently, they definitely ask one problem on Dynamic Programming?

Does anyone know of a good resource for collection of DP problems in C along with solutions? I know what DP is & have used it on an occasion or twice. However I feel to crack a DP problem in test, prior practice of typical problems will make it easier to approach.

Any good resources or problem sets with solutions in C will be highly appreciated. Thanks.

Answer 1

Okay, so I really hope this doesn't count as "shameless self-promotion," since all of these links are to code snippets I've posted on my personal site. If this is inappropriate, please let me know and I can take them down.

Here are a few fun DP problems that are pretty much classics:

1. Minimum edit distance: Given two strings A and B, find the shortest number of edits (insertions, deletions, or substitutions) necessary to convert A into B. This is called the Levenshtein distance. (My solution)
2. Optimal sequence alignment: Given two strings A and B, find the minimum number of gaps that must be inserted into the sequence to align A and B. This is called the Needleman-Wunsch algorithm. (My solution)
3. Single-source shortest paths: Given a directed graph G and a single node s, find the lengths of the shortest paths from s to each other node in the graph, assuming edges can be positive or negative but that no cycles exist. This is the Bellman-Ford algorithm. (My solution)
4. All-pairs shortest paths: Given a directed graph G, find the minimum distances between all pairs of nodes. This is the Floyd-Warshall algorithm. (My solution)

Hopefully this is somewhat useful, and best of luck tomorrow!

Answer 2

The Topcoder website is amazing. Not all of the problems use DP, but many do. Free full access to all problems from past competitions, which are at 3 different difficulty levels, as well as after-match explanations of every single problem from the problem author. Not only that, but you can quickly dig up the source code solution submitted by any coder in the competition.

Haven't been back there for a while, but they allow at least C++, Java, C# and I believe several other languages now.