If I remember dynamic programming correctly, what he did is the following.
You solve the problem WC(C, S, G, V, c, s, g, v),
which gives you the worst case number of turns for getting 8 Provinces, when your deck starts with C Copper, S Silver, G Gold, V Victory cards in deck and c Copper, s Silver, g Gold, v Victories in the discard.
For all reasonable values of C,S,V,G,c,s,g,v as described above. Now some instances of this problem are pretty easy, for example WC(C, S, G, 11, c, s, g, v) is 0 for all values of CSGcsgv.
So you start with these, save the result, and try to solve WC(C, S,G, 10, c, s, g, v). But that's now also not so difficult, you just look for the worst-case, given this starting points, to gain a Province. You calculate all of them, and go to WC(..., 9, ...), and so on, until you have WC(7, 0, 0, 3, 0, 0, 0, 0), which is what you where looking for.
About like that. Probably you do it recursively starting form WC(7, 0, 0, 3, 0, 0, 0, 0) and only calculate the WCs you really need, but more or less that's the idea. The important point is that you, in all the branches you get from this starting point, will always be in one of the states described above, and so you only need to calculate each state once, and you are finished when you have calculated WC for all states (or probably a bit earlier).
Edit: So what you do is having a giant/small (depending if you are a human or a computer) table in which you navigate, the cell you are in represents the state of your deck. Once you are in a cell in which you have already been, you can take the short-cut and use just the result from last time.
Edit2: So for me, that counts as examining all paths in this tree.
Edit3: The "small" set from the perspective of the computer actually has 1.5GB, so small is relative...