Recursive With Memoization


  • 0
    C

    I tried to solve the problem recursively. Without using memoization, the correct answer was achieved, but not within acceptable time. Therefore, I chose to include memoization, and that worked. The solution, in Java, is as follows:

    private int[] memo = new int[1000];
        
        public int minSteps(int n)
        {
            if(n == 1)
                return 0;
            return stepCount(n, 1, 1, 1);
        }
        
        public int stepCount(int n, int c, int s, int acc)
        {
            if(acc == n)
                return s;
            else if(acc > n || s >= 1000 || (memo[acc] != 0 && memo[acc] <= s))
                return Integer.MAX_VALUE;
            else
                return Math.min(stepCount(n, c, s + 1, acc + c), stepCount(n, acc, s + 2, acc << 1));
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.