Dynamic Programming, Cell Mitosis Problem

#1

In the video, bhaiya said that in the case when i is even, we will only consider the case when it is formed from either i/2 or i-1. He said we’ll ignore the case of i+1 as it’s cost will be higher. I don’t understand this. Why would it higher?

For eg.
Suppose we want to make 14
Doubling Cost is 1
Incr Cost is 50
Decr Cost is 50

1 -> 2 -> 4 -> 8 -> 16 -> 15 -> 14
Cost: 1 x 4 + 50 + 50 = 104

Now, here we can’t come to a lower cost without going through 15.

PS: I have checked this ans but it wasn’t still clear:

#2

Hi @tanmay777,

1 -> 2 -> 3 -> 6 -> 7 -> 14

Total Cost = 1 + 50 + 1 + 50 + 1
= 103

We don’t need to cross 15.

#3

Ohh thanks Puneet. But I still can’t build the intuition for this. Can you prove somehow that i+1 cost will always be higher for even case.

#4

@tanmay777,

x = doubling cost
y = increase
z = decrease

Let’s assume that for an even index third operation is optimal i.e dp[i] = dp[i+1] + z

Now, let’s compute dp[i+1] as (i+1) is odd, it is obvious that there are two ways either increment dp[i] or ( double dp[i/2 + 1] and then decrement ).
But initial is not possible so, the only way left is, dp[i+1] = dp[i/2 + 1] + x + z

Now,
dp[i] = min({ dp[i/2] + x, dp[i-1] + y, dp[i+1] + z })
dp[i] = min({ dp[i/2] + x, dp[i-1] + y, dp[i/2 +1] + x + 2*z})

If dp[i/2] <= dp[i/2 + 1] then obviously third term can be ignored.

But if dp[i/2] > dp[i/2 + 1] then, in worst case scenario,

dp[i/2] = dp[i/2 + 1] + z
dp[i/2] + x = dp[i/2 + 1] + z + x
dp[i/2] + x < dp[i/2 + 1] + z + x + z
Again, we can again ignore the third term.

I hope you get the intuition.

#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.