My favorite dynamic programming problem is computing the percent of relatedness between two people, given a set of people and a partial graph of parenthood among them (with the assumption that any relatedness not implied by the graph is zero). If seems very confusing at first, but then you realize that if A is not a descendant of B, rel(A,B)=(rel(A,father(B))+rel(A,mother(B)))/2, which allows you to compute all relatedness values from top to bottom of the graph as fast as possible.