I am not able to understand the process how are we calculating the answer ,can you please dry run any test case???
Doubt in the question
You can divide a number into 3 posssible parts n/2, n/3,n/4
12 can be exchanged for 12/4 + 12/3 + 12/2 summing to total value 3+4+6=13 which is the maximum you can get.
General case:
From the problem definition, say f (n) = ways to compute the change.
- f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4)) (by definition).
- f (0) = 0 (Base case)
Writing a simple recursive solution will time out due to exponential complexity i.e. O (3^n ).
Writing a linear dynamic programming solution using arrays will exceed memory limit since N can be 10^9 in worst case.
To circumvent both of the a aforementioned problem, we can use maps and memoization.
Note: This is one of those problems where state space is extra large and memoization only explores space what is needed unlike bottom up dynamic programming which needs one to visit all the state space, memoization is the preferred solution in this case.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.