Bottom up approach

#1

please explain in bottom approach(pure dp) whay are we writing 1 +dp[curNum/3]?what does that signify?

#2

See we have three options either subtract 1 , divide by 3 if divisible , divide by 2 if divisible , so from every n we have to go to 1. For bottom up we need base case and here base case will be if we are at 1 then dp[1]=0, if we are at 2 ,dp[2]=1 because we can subtract 1 or divide 2 by 2 to reach 1, let if we are at 3,
then we can reach 1 in one step using (n/3).
So we start building our dp array from 4 to n , at every time we have 3 options either n is divisible by 3,or 2, n-1, so we take minimum of those and add 1 because we have taken 1 step.
dp[currNum]=1+dp[curNum/3] signifies that we are at a position which is divisible by 3 so we jump from that currNum to currNum/3 and for this we jump we are adding 1 to our ans.

You can refer to the code both iterative and recusive if tou have any doubt further.

#3

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.