how we reach to the conclusion that the I is depend on I/2 i-1 and I+1 ??
Cell mitosis dynamic programming
hey, maybe ur question is
how is it dependent on
(i+1)/2 , i-1
and
i/2 and i-1
it is because when we fill it bottom up, we think of the states of how we are gonna reach this state
so, the possibilities are
from some state j, we increase one, so that is i-1
from that state we have doubled that is i/2
from that state we increase one and then double the cells
No I am talking about in question it is given that it can take position 2*i I+1 and i-1 so how we can conclude that it depends upon I/2 i-1 and I+1??
it is because when we fill it bottom up, we think of the states of how we are gonna reach this state
when we are filling a particular state, we analyse the previous states how can we reach this state
so for any state
only those three operations are available
so we must have done, either those operations or a combination of those operation to reach this state and hence we can say that this state is dependent on those three previous states
agar tumhe mne kaha
ki 4 kilo apple lao
first u buy 1 kg and then 1 more kg and then 1 more kg and again 1 more kg
toh har state uske previous state pe dependent hai i-1 ke
ab iska ulta nhi kr skte,mtlb agar 4 kilo hai and u can only buy more, can u ever reach 3 kg??
toh isliye ham chote state se bdi state m relation nikalke use, is manner m fill krte hai
Nicely explained sir… Can we not fill the table from n to 1 ?? In this way I can get the value in this form as question??
see, suppose u had 10 cells
now u can either go,+1 , -1 or i/2
but what if the best way would have been something like
u first take 2 more cells and go till 12 and then go to 6, now how will u contemplate this without trying everything, maybe u had to go till 14 maybe 16,
where will u end it? how will u end it?
is it not better to judge the best way to reach 10 instead of the opposite?
I did not get it can you clear it again why we are going to 14 and 16 ??
i was just taking a random example that this could be a case
“MAYBE”
that going from 7 to 14 to 10 is a more optimum one
than from 6 to 12 to 10
just a random example
so basically you are trying to say that if we compute by reverse order we cannot try all possible vlues??
yes, that is exactly what i mean to say
i would rather say
we cannot get all OPTIMUM vlues
how to decide that we can compute by reverse or not because in some of dp problem i was able to solve by everse as well as by front??
as a general practice, most question will be solved from front
some questions that do not depend on a previous state
or where starting from the end is optimum can be solved from reverse
there is no hard and fast rule for it, it depends on question to question
most question will be solved from front
so if we are solving a problem we have to check that in that position let say i… we are getting all possible optimum ans or not ?? i understood this…
Once u solve a few problems, and are able to form the recursive relation
it will come to u more easily what is the most optimum path
like in this problem i got the intuition that if i start from reverse if i am at ith position and want the optimal anser for ith position i want i+1 i-1 and 2ith position but 2ith can be out of range and i-1th we havent calculated and i+1th we can get from table thats the one thing i am feeling that thats why it can not done by reverse order what is your opinion about this??..
that is the correct intuition
everybody can have different intuition on the same problem
it is very subjective on the coder
1 Like
ohk sir thanks you cleared it well…
if your doubt is solved, please mark it as resolved
cell mitosis.
I have done this through memoisation and it passed 3 taste cases.
i also figured the error but I m not able to resolve it.
plz help as soon as possibel
code. https://ide.codingblocks.com/s/262439.