Here is my code :
2 test cases seem to fail with this.
Here is my code :
2 test cases seem to fail with this.
hi @Prashant-Kumar-1947183015386369, you are storing only one state of your solution
i.e. but your solution also depends on m so you need to have multidimensional dp to store m and n at every state
refer code for better understanding : https://ide.codingblocks.com/s/243320 (corrected code)
In case of any doubt feel free to ask
mark your doubt as resolved if you got the answer
Hi Abhijeet, Thank you very much for your response. Can you clarify one thing for me? - How do we know how many states are there in a dp problem? For example, in fibonacci also the solution depends on previous two values, but one dimensional dp suffices there.
Formally state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space.
For example: In this, we define our state by two parameters n and m i.e DP[n][m]. Here DP[n][m] tells us the number of ways we can get change of n if we have infinite supply of m distinct valued coins with us. Therefore, here the parameters n and m together can uniquely identify a subproblem for the coin-change problem.
So, our first step is always deciding a state for the problem after identifying that the problem is a DP problem.
As we know DP is all about using calculated results to formulate the final result.
So, our next step is to find a relation between previous states to reach the current state. i.e. forming relations .
In case of fibonacci series as you said the solution depends on previous two values. but we only need to know about one parameter that is index as for dp[index] if we know dp[index-1] and dp[index-2] we can compute dp[index], but in coin-change problem n and m are independent entities that;s why two different states , say, if we could have computed a unique value of m using n i.e m=f(n) then we would have reduced the parameters to n only and computed m .thus solving the problem using single dimension array dp[n]
long story short , understand about states is something that comes naturally through practice
you can solve same problem using 3 .4 or any number of states but minimizing the states to uniquely identify the subproblem is the main task and which would come to u naturally through experience so practice as much as you can .
Hi Abhijeet, Thank you for your elaborate response. I appreciate that!