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[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 :)

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[100][100]; 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[0][i] = 1;         for (u = 1; u <= 99; u++) dp[u][i] = 0;     }     ...     return 0; } 

Last questions

how do i remove the switch on my home screen?
how to edit the JS date and time to update atuomatically?
How to utilize data stored in a multidimensional array
Powermockito not mocking URL constructor in URI.toURL() method
Android Bluetooth LE Scanner only scans when phone's Location is turned on in some devices
docker wordpress container can't connect to mysql container
How can I declare a number in java that is more than 64-bits? [duplicate]
Optaplanner solutionClass entityCollectionProperty should never return null error when simple JSON object passed to controller
Anylogic, get the time a pedestrain is in a queue
How do I fix this syntax issue with my .flex file?
Optimizing query in PHP
How to find the highest number of a column and print two columns of that row in R?
Ideas on “Error: Type com.google.firebase.iid.zzav is referenced as an interface from com.google.firebase.messaging.zzd”?
JCIFS SmbFile.exists() and SmbFile.isDirectory() return false when it exists and I can listFiles()
PHP total order
Laravel booking system design
neural net - undefined column selected
How to indicate y axis does not start from 0 in ggplot?
Fragments in backStack
Spinner how to change the data