Min steps to one - bottom up not giving correct ans

#1

Why my bottom up function for min steps to one is not giving correct output. I have gone through several times through my code but could not come out with any conclusion . What is wrong behind the scenes? https://ide.codingblocks.com/s/112070

#2

@LPLC0114
You should reinitialise op1 , op2, op3 as INT_MAX in every iteration of the for loop.
Change it to this.
for(int i = 4;i<=n;i++)
{
int op1 = INT_MAX, op2 = INT_MAX, op3 = INT_MAX;
if(i%3 == 0) op1 = 1 + dp[i/3];
if(i%2 == 0) op2 = 1 + dp[i/2];
op3 = 1 + dp[i-1];
dp[i] = min(op1,min(op2,op3));
}

#3

Now it’s working fine bt why are reinitializing op1, op2, op3> what’s the need?

#4

@LPLC0114
We need to reinitialise op1,op2 and op3 everytime as INT_MAX for every iteration or otherwise it would take its previous values and give us wrong answers.
Take a look at your Top-Down Approach function. Each call to Top Down function is equivalant to one iteration of Bottom Up Approach. You initialise op1,op2 and op3 new for every call in Top Down approach since every value of n requires seperate computation.
Same is the thing with Bottom Up approach loop. If you do not reinitalise it , if op1 had got a lesser value in previous iteration , it would take it and continue with it for the next iteration as well even though , it might not have been a valid answer for the next iteration.

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