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;
}