I didn’t get the condition, when index in DP array is even…
So,
dp[i]=min(dp[i/2]+x, dp[i-1]+y)
where x and y are the respective cost.
My doubt is that we’re not considering option from index (i+1),
because it will have more operations than those 2 operations but how?
hello @Kinjal have you seen the prateek sir’s video for this question .
he has explained this question very deeply in the video with code :
Yes bhaiya. I have seen that content but still I didn’t get this doubt…
if dp[6] we are computing then, we should look for dp[5] and dp[4] but why not dp[7]?
Because, still we are computing for the odd index in the DP array at the end, so why can’t we include that odd condition when we are computing for even index i.e. dp[6]
Prateek Bhaiya narrated the idea that we can’t include dp[7] to compute dp[6] because dp[7] will take more operations than dp[4] and dp[5] and our task is to find minimum operations at the end.
But, I didn’t get the idea, how dp[7] will take more operation than dp[5] and dp[4] to compute dp[6]…?
Even Condition: when i is even
dp[i]=min( dp[i/2]+x , dp[i-1]+y )
Odd Condition: when i is odd
dp[i]=min( dp[i-1]+y , dp[i/2]+x+z )
dp[7] is itself odd so it woudnt give us the direct muktiple of 2 so thats why are not considering to be the way .
odd index will always give the longer way to us .
What I think that may be the reason is present in this small equation. Because here we are adding 2 costs variable so it’s no brainer that it’ll give maximum cost than other operations.
Can we solve this problem using Top-Down Approach?
some quesions have some tricks which made to implement their codes in a better and efficient way .
.
HappyLearning !!
Okay, you meant that bottom up approach is the better and efficient way for this problem…!?
Tell me about the base case for this problem,
why dp[1]=0 ?
if you start with 1 i mean if you intially have 1 then do even have to perform any operation in budding your final cells to 1 ?
No I guess…
In this type of DP problem, there has overlapping subproblems but we never consider dp[i+1] state to compute dp[i] irrespective of i is even or odd and still it’s given in the question…what is it mean? Is it just to make the question complicated and hard?
Elaborate what like how dp[1]=0…
i am asking you to please elaborate your doubt ?
According to our problem, we have to find minimum cost to make N cell from single cell so we have 3 options,
So, to compute all the indexes inside dp[] array, we never used option 3 particularly. So it’s just make the whole problem difficult…that’s what I think. Just a distraction
@Kinjal at first you will be confused in lot of dp questions about their implementation but with time and practice you will be very much comfortable with the concept and building of the logic .
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.