How to use memoization on this recursion

Question

Hi

Please refer code below:
It works fine but i just want to use memoization along with this recursion to avoid extra calls.

Can anyone suggest ?

Is it like

Vector<int> dp(n+1,-1) or something different ?
https://code.sololearn.com/cLpe1RZICGy6/?ref=app

Answer 1

Yes, you can use memoization to avoid redundant function calls and improve the performance of the algorithm.

You can define a 2D vector dp of size (num+1) x (coins.size()+1) and initialize all its elements to -1. Then, you can modify the helper function to use memoization by first checking if the result for the current num and idx has already been computed and stored in dp. If so, you can return the cached result directly. Otherwise, you can compute the result recursively as before and store it in dp before returning it.