Almost five Dynamic Programming problems

I'm following edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, and I've just completed week five, that is about Dynamic Programming. To pass it, I had to solve a few problems, presented in this pdf.

Here I present them, my annotated python solutions in following posts.

Money Change Again

Given an integer amount, and an (infinite) numbers of coins of given denomination, return the minimum number of coins needed to change the full amount.

In the (sort of disappointing) previous week, they presented a greedy approach to this problem. When it works, it is cool and fast. However, to use it we have to prove that each greedy selection is safe. And that it is true only for some set of available denominations. Otherwise we must follow a different approach. And here enters Dynamic Programming.

It is a simple problem, good introduction to this technique.

Primitive Calculator

We should get to a given integer, starting from 1 and applying just a limited number of operations. Can we minimize this number?

If you see the similarity with the previous problem you have already done large part of the job.

Edit Distance Between Two Strings

Given two strings, returns their edit distance. This is a classic problem that could be solved by Dynamic Programming. The two previous one need a linear cache, here we should push our intermediate solutions in a matrix. Things are a bit more complicated, however you could find lot of documentation about this problem on the net.

Longest Common Subsequence

Given two sequences, find the largest shared subsequences. It is close to the previous problem, here we are interested just in commonalities between the two input sequences. Similar structure, some implementation differences. Also this problem is well known and studied.

Longest Common Subsequence of Three Sequences

Extension of the previous one, now we have three sequences to be compared. The point is not so much in Dynamic Programming anymore - since the structure is essentially the same - but how the programming language you use for implementing the solution manages a three-dimensional matrix.