 Categories: java, c++, c, c++14

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

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);     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; // 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);     int u;     dp=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 :)

## All answers to this question, which has the identifier 60946213

The best answer:

You are trying to memoize the result for a particular value of `n` but you are forgetting `m`. You need a 2-dimensional memo table. Something like.

``int dp; int count(int S[], int m, int n) {     ...     if (dp[n][m] != 0) return dp[n][m];     dp[n][m] = count(S, m - 1, n) + count(S, m, n - S[m - 1]);     return dp[n][m]; }  int main() {     ...     int u;     for (int i = 0; i < 100; ++i) {         dp[i] = 1;         for (u = 1; u <= 99; u++) dp[u][i] = 0;     }     ...     return 0; } ``