2
$\begingroup$

I am new to the concepts of recursion, backtracking and dynamic programming.

I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there is a relation between memoization being applicable ONLY to top down recursive algorithms. Any explanation on the same would be greatly appreciated.

The Background to this question:

I have a naive inefficient recursive solution(below) a and wish to incorporate memoization but don't know if it is possible.

Problem Statement: Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, Print the number of ways (non-distinct sets) this can be achieved.

Ex: Ex: N = 4 , S = {1, 2, 3}

1 1 1 1 
1 1 2 
1 2 1 
1 3 
2 1 1 
2 2 
3 1

My code:

public static int change(int n, int count, int sum) {

        if(sum == n) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        for(int i = 1; i <=3; i++) {
            sum = sum + i;
            count += change(n, 0, sum);
            sum = sum - i;
        }
        return count;
    }
|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you double check the terminology, "recursive bottom up algorithm"? Bottom-up means from nearer and smaller problems to further and larger problems. If such an algorithm is also recursive, that would imply solutions to smaller problems are based on solutions to larger problems, which looks like unreasonable. $\endgroup$ – John L. Mar 1 '19 at 7:26
  • $\begingroup$ I will remove the word bottom up as it may ne causing confusion $\endgroup$ – Spindoctor Mar 1 '19 at 11:30
  • $\begingroup$ cs.stackexchange.com/q/2057/755 $\endgroup$ – D.W.♦ Mar 31 '19 at 16:04
1
$\begingroup$

Memoization can be applied to any function. Whether it helps with a given program or not depends on how often the function is called with the same parameters.

You don't specify what your recursive solution is. Typically for this problem is imagine something like

change(total, denominations) = sum of change(total - k m, denominations \ m) where m = max(denominations) over k m <= total

Can change be called with the same arguments more than once? Yes. For instance if you're trying to make change for $1 you might take two quarters and one dime or you might take no quarters and six dimes. In either case you'll next be asking for the numbers of ways to make forty cents with a dime and a nickel. So you can save something by calculating this once and storing the result.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you, I wasn't sure if I could post the code but I have updated the question. I see that you have described a solution but you start from the total and work your way down. Is this not a top down approach? If you see my code, I sum starting from a specified value and keep adding to see which combinations sum to the desired amount. I figured mine works form the bottom up, unless I have compeltely misunderstood the two concepts. $\endgroup$ – Spindoctor Feb 28 '19 at 22:56
  • $\begingroup$ This code doesn't make a lot of sense. For instance, you have a parameter called "count," but the way your program is written this will always be zero. I'm also not sure what you mean by "bottom-up recursion." Typically bottom-up approaches are done iteratively. Why don't you try to get your algorithm working first and then try to work on optimizing it? $\endgroup$ – Daniel McLaury Mar 1 '19 at 2:46
  • $\begingroup$ The code works fine and the count is 0 so as to reset the count for a new set of combinations. What I meant by bottom up is i am not starting from the total and recursing with the balance i.e., sum - i. I am rather adding to the sum when I pick a number. You also mentioned that a bottom up approach is typically iterative. Is there a link you can share stating this???? $\endgroup$ – Spindoctor Mar 1 '19 at 11:33
  • $\begingroup$ I have managed to memoize the algorithm above and found this question about the difference between dynamic programming and memoization. Since I have "memoized" and it's in a tabular form, I would not consider it dynamic programming as its just a memorization of the previous answer and dynamic programming means - building of an optimal solution from a previous optimal solution using memoization. stackoverflow.com/questions/6184869/… $\endgroup$ – Spindoctor Mar 14 '19 at 23:10
  • $\begingroup$ Memoization can be applied to any pure function (but not to functions that have side effects or memory or that depend on global state). $\endgroup$ – D.W.♦ Mar 31 '19 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.