Wrong output in Money Change problem

#1

Sir, My code is giving wrong output. I tried to solve this question using top down DP.

I think there is some problem in the base case. Kindly look into it.

Link to my code : https://ide.codingblocks.com/s/610505

#2

your approach is not correct
you have to consider two case
either include the current denomination or not include

also you have to use 2D dp here for memoization
because there are 2 parameters n and m

#3

sir, i have solved it using bottom up dp using 2d arrays. The sample test cases are giving correct input but in all other test cases i am getting run time error and i am not able to figure out the exact problem.

#4

Link : https://ide.codingblocks.com/s/612544

#5

2 problems in this code

  1. dp arary (ways) should be decalare globally bec size of array is large 10^6 X 500
  2. you have to take mod at each step before storing in dp array otherwise data will overflow and after that taking mod is useless

Also
there is no need to use long long int
sorting is not required

Modified Code

#6

yes sir…corrected…but now it is giving memory limit exceeded error in test case 1 and 6. I have also tried using 2 d vectors but still there was error