Java DP straightforward solution with detailed comments : 58ms


  • 0
    P
    public class PerfectSquares {
    
        private int[] memo = null;
    
        /**
         * Algorithm is as follows.
         * Given N, attempt to calculate all possible scenarios by subtracting largest
         *  possible squared number to smallest, call this value L, and repeat the process
         *  on N-L. On each attempt,save the current steps if better solution is
         *  found and do not process if better solution is already found.
         *
         * memo array keeps track of steps to taken to get to n by subtracting possible
         *  squared number that's less than N. (e.g. memo[3] = minimum steps taken for
         *  N to get to 3) Because of this property memo[0] will be steps taken for N to
         *  get to 0, which is the answer we are interested in.
         *
         * @param n
         * @return
         */
        public int numSquares(int n) {
    
            // Integer.MAX_VALUE means not solved yet.
            memo = new int[n+1];
            for(int i = 0; i < memo.length; i++) {
                memo[i] = Integer.MAX_VALUE;
            }
    
            findMinSquare(n, 0);
    
            return memo[0];
        }
    
        private void findMinSquare(int n, int steps) {
            /**
             * There are two conditions that we know when NOT to proceed further
             * 1. Problem is solved previously and has equal or more closer answer
             * -----> (memo[n] <= steps)
             * 2. Number of steps to get n is equal or less than the minimum that
             *     we already calculated
             * -----> (steps >= memo[0])
             */
            if(memo[n] <= steps || steps >= memo[0]) {
                return;
            }
    
            int largestFit = (int) Math.floor(Math.sqrt(n));
    
            /**
             * Try different solution. Lesser closer solution will be terminated because
             *  of base condition in the method
             *
             */
            for(int i = largestFit; i >= 1; i--) {
                findMinSquare(n - i*i, steps + 1);
            }
    
            /**
             * Is current number of steps smaller than previously calculated steps?
             * - If yes, then we memo it
             *
             */
            if(memo[n] > steps) {
                memo[n] = steps;
            }
        }
    }

Log in to reply
 

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