Storing partial results, Dynamic Programming

Today, I tried to resolve a programming puzzle; which is a bit different than usual problems. Generally a problem like Finding fibonacci series Nth number, has two variants of solutions, Recursive and Iterative. Recursive solutions needs solution for sub-problem first and makes up the complete solution in bottom-up manner.

Fib(n) = Fib(n - 1) + Fib( n -2 )

Ignoring base cases, this would be complete recursive solution. Calculating in this way, would be easier for us to implement, but computation complexity would be huge. For instance, not only Fib(n) calculates Fib(n-2), Fib(n-1) also calculates the same. Same calculations would recur several times. Cause of this is not storing the computed result. For this kind of problems, obvious way to efficiently solve is to store intermediate results. This leads to Iterative solution.

Fib[n] = Fib[n - 1] + Fib[n - 2]

Note: Array is being accessed, not any more recursive function calls. All calculations happen only once.

Computation complexity comes down to O(n). This is one way of viewing Space Time complexity trade off. We successfully traded off space for Time.

There are some problems, don't need all partial results. In that case calculating all the intermediate values would be waste of time. Think about space complexity also.

One such example, taken from CodeChef

One strange bank will provide you three possible coins for a coin of denomination $N, as follows:

$N/ 2, $N/ 3, $N/ 4. N is an integer.

Changing coin would be profitable, for denominations like $12, $24. But for 3, this would cause a loss of $1. (3 /2 + 3 / 3 + 3/4) = $2.

What would be the maximum profit possible with $X.

We can't solve this problem iteratively as we do need result for X, not for 1, 2 ... X. Since X can be considerably big, we can't store all intermediate values also. At last, there is no need for all intermediate calculations for calculating Xth value.

This suggests us to go for Recursion based one. But we know storing intermediate results would help to avoid same calculations several times. So, storing only a part of intermediate results in a Map, or a Hash Table or a Simple array would be very useful.