Given a number n, count minimum steps to minimize it to 1 according to some conditions || DP || EASY
Vidhu
5837

Given a number n, count minimum steps to minimize it to 1 according to the following criteria:
If n is divisible by 2 then we may reduce n to n/2.
If n is divisible by 3 then you may reduce n to n/3.
Decrement n by 1.

Greedy Approach (Doesn’t work always) :

As per greedy approach we may choose the step that makes n as low as possible and continue the same, till it reaches 1.

while ( n > 1)
{
    if (n % 3 == 0)
        n /= 3;    
    else if (n % 2 == 0)
        n /= 2;
    else
        n--;
    steps++;
}

If we observe carefully, the greedy strategy doesn’t work here.
Eg: Given n = 10 , Greedy –> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ).
But the optimal way is –> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ).
So, we must think of dynamic approach for optimal solution.

f(n) = 1 + f(n-1)
f(n) = 1 + f(n/2) // if n is divisible by 2
f(n) = 1 + f(n/3) // if n is divisible by 3

Recursive Code

	int minSteps(int N) 
	{ 
	    if(N==1)
	    return 0;
	    int a=INT_MAX,b=INT_MAX, c=INT_MAX;
	    if(N%2==0)
	    a=1+minSteps(N/2);
	    if(N%3==0)
	    b=1+minSteps(N/3);
	    c=1+minSteps(N-1);
	    
	    return min(a,min(b,c));
	    
	}

Memoization

int dp[1000];
	int solve(int N)
	{
	    if(N==1)
	    return 0;
	    
	    if(dp[N]!=-1)
	    return dp[N];
	    
	    int a=INT_MAX,b=INT_MAX, c=INT_MAX;
	    if(N%2==0)
	    a=1+minSteps(N/2);
	    if(N%3==0)
	    b=1+minSteps(N/3);
	    c=1+minSteps(N-1);
	    
	    dp[N] = min(a,min(b,c));
	    return dp[N];
	}
	int minSteps(int N) 
	{ 
	    memset(dp,-1,sizeof(dp));
	    return solve(N);
	}

Bottom Up DP

	int minSteps(int N) 
	{ 
	    int dp[N+1];
	    
	    dp[0]=0,dp[1]=0,dp[2]=1,dp[3]=1;
	    
	    for(int i=4;i<=N;i++)
	    {
	         int a=INT_MAX,b=INT_MAX, c=INT_MAX;
	         
	         if(i%3==0)
	         a=1+dp[i/3];
	         if(i%2==0)
	         b=1+dp[i/2];
	         c=1+dp[i-1];
	         dp[i] = min(a,min(b,c));
	    }
	  
	    return dp[N];
	}
Comments (7)