Cell Mitosis dp problem webinar

#1

plz tell the approach to solve this problem.
i am thinking of
dp[i]=min{dp[2i]*a, dp[i+1]*b, dp[i-1]*c}…

#2

Hi

No recursion will not be like this
approach will be like

if i is even
dp[i]= min(dp[i/2]+x,dp[i-1]+y} ;

if i is odd
dp[i]=min(dp[i-1]+y,dp[i+1/2]+x+z} ;

for more explanation have a look at video, it’s in the course ( advance dp cell mitosis) , if you have doubt in approach please do post.

Hit like if you get it
Cheers

#3

Hi
Juhi as you are not responding to this thread i’m marking this as resolved you can reopen it later if you still have doubt.

#4

I think the solution given by him(Naveen) is wrong cause take the case of to reach 6.
we can reach 6 in the following ways:-
1.) 1->2->3->4->5->6. Cost will be= min(x, y)+4y. min(x, y) is to reach 2 cause 1+1=2 and 1*2 =2.
2.) 1->2->3->6. Cost will be= min(x, y)+y+x.
3.) 1->2->4->5->6. Cost will be= min(x, y)+ 2y.
4.) 1->2->4->8->7->6. Cost will be = min(x, y)+2x+2z.

According to the solution given by him(Naveen), to reach 6 we should only consider path_2 and (path_1 or path_3) path but the 4th path can also be a solution.
if solution of this inequality exists then the 4th path will be the solution.
cost_1+cost_2+cost_3 > 3 (cost_4)
3min(x, y)+ 7y+2x > 3min(x, y)+6x+6z
7y+2x > 6x+6z
7y > 4x+6z
Clearly the solution to this inequality exist and hence the method mentioned by him is wrong.

Solution:- there should be a upper bound on the number of cells and then. after than simple apply Dijkstra and find the shortest path from 1 to N.

#5

x is the cost of doubling. not half. Please read the question first.

#6

It will cause an infinite loop as for i=1 it will call for function with i=2 and then it will again call i=1. Also, the solution given in video is incorrect as they use x as the cost of halving instead of doubling.