About DP state mentioned

#1

what is meant by the state of a dp? how to understand which one is the DP state?

#2

State of a dp is nothing but memoization or to remember the previous calculated state, such that we don’t recalculate it multiple times resulting that our program’s time complexity reduces.

Whenever you see a recursive function in which the states are calculating them multiple time, you have to use DP such that we don’t recalculate a single function multiple time.
There’s a video name Fibonacci in dp section of your course.I would suggest you to see that video for crystal clear concept of DP.

#3

Dp concept I understood but in the coin chng prblm bhaiya mentioned that N is the state of dp hence it is 1D dp prblm that I didn’t understand. What is state of dp and how to understand whether it is 1D Or 2D dp qstn?

#4

Since N is the value which we have to make using an array of given coins to us(let it call array a). So when you will subtract N - a[i] you will get a certain amount and let that amount be y. Now with some other jth element when you will subtract N - a[j] you might get a state where you have to treat N with a[i] and to calculate again we use DP.

If N== 0, then 0 coins required.
If N > 0
minCoins(coins[0…m-1], N) = min {1 + minCoins(N-coin[i])}
where i varies from 0 to m-1
and coin[i] <= N

This is Dp of state that if you get any state multiple times and you just store it somewhere so that you can avoid calculating it multiple times. Also in recurrence relation if you see two dependent variables then you can call it a 2-d DP but if there’s only a single factor affecting the recurrence relation. Then we will call it 1-d DP
Here , only factor affecting the recurrence relation is value of N, so it’s a 1-d Dp .

#5

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.