# Getting wrong result while applying DP memoization approach in recursive overlapping problem

Akhil Mittal. The question was asked: Mar 31, 2020. 08:24

1 answer

I was applying DP memoization approach in recursive Coin Change problem. But I am getting wrong answer while applying memoization approach(top to bottom dp approach) to overcome the overlapping problem.

Below is the recursive solution(which is giving correct result) :

`#include<stdio.h> // Returns the count of ways we can // sum S[0...m-1] coins to get sum n int count( int S[], int m, int n ) { // If n is 0 then there is 1 solution // (do not include any coin) if(n==0) return 1; // If n is less than 0 then no // solution exists if (n < 0) return 0; // If there are no coins and n // is greater than 0, then no // solution exist if (m <=0 && n >= 1) return 0; // count is sum of solutions (i) // including S[m-1] (ii) excluding S[m-1] return count( S, m - 1, n ) + count( S, m, n-S[m-1] ); } // Driver program to test above function int main() { int i, j; int arr[] = {1, 2, 3}; int m = sizeof(arr)/sizeof(arr[0]); printf("%d ", count(arr, m, 4)); getchar(); return 0; } `

Below code is the memoization approach applied by me(giving wrong answer) :

`#include<stdio.h> int dp[100]; // Returns the count of ways we can // sum S[0...m-1] coins to get sum n int count( int S[], int m, int n ) { // If n is 0 then there is 1 solution // (do not include any coin) if(n==0) return 1; // If n is less than 0 then no // solution exists if (n < 0) return 0; // If there are no coins and n // is greater than 0, then no // solution exist if (m <=0 && n >= 1) return 0; //Memoization if(dp[n]!=0) return dp[n]; // count is sum of solutions (i) // including S[m-1] (ii) excluding S[m-1] return dp[n] = count( S, m - 1, n ) + count( S, m, n-S[m-1] ); } // Driver program to test above function int main() { int i, j; int arr[] = {1, 2, 3}; int m = sizeof(arr)/sizeof(arr[0]); int u; dp[0]=1; for(u=1;u<=99;u++) dp[u] = 0; printf("%d ", count(arr, m, 4)); getchar(); return 0; } `

I have checked a lot where/what i am doing wrong, but could not find it out. Please help to find out the mistake. Thanks :)