[Tutor] Euler Spoiler

Danny Yoo dyoo at hashcollision.org
Mon Jan 13 02:24:50 CET 2014


This sounds very much like a problem that demands trying to break the
problems down into subproblems, and then applying a
"dynamic-programming approach" to make it fairly easy to get an
efficient solution.  Such problems that are amendable to this approach
have a "substructure" to them so that the main problem breaks down
into smaller versions of the same problem.


As an example, Problem 15 on Lattice paths is a good one:

   http://projecteuler.net/problem=15

Here, the problem is asking: count how many paths there are in the n*n
grid.  A sub-problem of this is: count how many paths there are in the
(n-1)*n graph, and count how many paths there are in the N*(n-1) grid.
 Why are those particular subproblems interesting?  Because if you
have the answer for the (n-1)*n and the n*(n-1), then you add the
results of those two together, and you get the answer for the original
n*n case!


Another example of a dynamic programming situation is in Problem 18,

    http://projecteuler.net/problem=18

where we can decompose the problem of trying to find the path that
maximizes the sum from the triangle as a whole to the sub-triangles on
the left and right hand sides.


In your problem statement, you're trying to answer the question:

    Given some goal g, find all the ways to break change.

A subproblem of this is:

    Given some goal (g - x) for each x in the denominations, find all
the ways to break change.

That is, a trick to solving the problem is to treat 'goal' as a
variable, part of the problem statement that can be changed.


Are you familiar with the dynamic programming approach?  I'm sure
folks here would be happy to talk about it more and show concrete
examples; it's a very powerful tool.


More information about the Tutor mailing list