Minimum steps to minimize n as per given condition | Java program to minimize n to 1 by given rule in minimum steps ; function to calculate min steps ; base case ; store temp value for n as min ( f ( n - 1 ) , f ( n / 2 ) , f ( n / 3 ) ) + 1 ; store memo [ n ] and return ; This function mainly initializes memo [ ] and calls getMinSteps ( n , memo ) ; initialize memoized array ; Driver Code
import java . io . * ; class GFG { static int getMinSteps ( int n , int memo [ ] ) { if ( n == 1 ) return 0 ; if ( memo [ n ] != - 1 ) return memo [ n ] ; int res = getMinSteps ( n - 1 , memo ) ; if ( n % 2 == 0 ) res = Math . min ( res , getMinSteps ( n / 2 , memo ) ) ; if ( n % 3 == 0 ) res = Math . min ( res , getMinSteps ( n / 3 , memo ) ) ; memo [ n ] = 1 + res ; return memo [ n ] ; } static int getMinSteps ( int n ) { int memo [ ] = new int [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) memo [ i ] = - 1 ; return getMinSteps ( n , memo ) ; } public static void main ( String [ ] args ) { int n = 10 ; System . out . println ( getMinSteps ( n ) ) ; } }