#include
#include <bits/stdc++.h>
using namespace std;
//reccursive approach
int min(int x , int y)
{
return (x < y)?x:y;
}
int min_steps(int n)
{
if(n == 1)
{
return 0;
}
if(n % 6 == 0)
{
return min(min_steps(n-1) , min(min_steps(n/2), min_steps(n/3))) + 1;
}
if(n % 2 == 0)
{
return min(min_steps(n/2) , min_steps(n-1)) +1 ;
}
if(n % 3 == 0)
{
return min(min_steps(n/3) , min_steps(n-1)) +1 ;
}
return min_steps(n-1)+1;
}
//top down dp
int min_steps_TD(int n , int dp[])
{
if(dp[n] != -1)
{
return dp[n];
}
if(n%6 == 0)
{
dp[n] = min(min_steps_TD(n-1 , dp) , min(min_steps_TD(n/2 , dp) , min_steps_TD(n/3 , dp)))+1;
return dp[n];
}
if(n % 2 == 0)
{
dp[n] = min(min_steps_TD(n/2 , dp) ,min_steps_TD(n-1 , dp)) +1 ;
return dp[n];
}
if(n % 3 == 0)
{
dp[n] = min(min_steps_TD(n/3 , dp) , min_steps_TD(n-1 , dp)) +1 ;
return dp[n];
}
dp[n] = min_steps_TD(n-1 , dp)+1;
return dp[n];
}
//bottom up approach
int min_stepsBU(int n)
{
int *dp = new int[n+1];
memset(dp , -1 , sizeof(dp));
dp[1] = 0;
for(int i = 2 ; i <= n ; i++)
{
if( i % 6 == 0)
{
dp[i] = min(dp[i-1] , min(dp[i/2] , dp[i/3]))+1;
}
else if(i%2== 0)
{
dp[i] = min(dp[i/2] , dp[i-1])+1;
}
else if(i %3 == 0)
{
dp[i] = min(dp[i/3] , dp[i-1]) + 1;
}
else
dp[i] = dp[i-1] +1;
}
return dp[n];
}
int main(void)
{
int n = 100;
cout<<min_steps(n)<<endl;
int dp[n+1];
memset(dp , -1 , sizeof(dp));
dp[1] = 0;
cout<<min_steps_TD(n , dp)<<endl;
cout<<min_stepsBU(n )<<endl;
}