The Bytelandian Gold Coins problem, officially published in SPOJ, concerns computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.
The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin —
Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin .
From the above interpretation, it is evident that the maximum achievable dollars, (from the exchange of coin ) can be computed as follows.
It effectively demonstrates an optimal substructure and therefore, hints to a dynamic programming (DP) technique to solve it. That is, for a coin , the optimal value of dollar is given by the following function.
We employ a top-down DP approach, as it seems more efficient than a bottom-up approach in this context. It is due to the fact that a bottom-up approach generally requires an OPT table to persist results of smaller subproblems. As in this case, the value of can be very large (i.e., , a bottom-up DP would require a very large array, and performs more computations. Hence, for the overlapping subproblems, we employ memoization.
The following code snippet outlines the implementation of
Full source code of the solution can be downloaded from this gist. Please leave a comment if you have any question/suggestion regarding this post.