52ms DP solution in Java


  • 0
    I
    public int numSquares(int n) {
        
        int[] lns = new int[n + 1];
        lns[0] = 0;  // base case for n = 0
        
        for (int i = 1; i <= n; i++) {
            int square;
            int leastNumSquares = lns[i - 1];
            
            for (int squareBase = 1; (square = squareBase * squareBase) <= i; squareBase++) {
                int candidate = lns[i - square];
                leastNumSquares = Math.min(leastNumSquares, candidate);
            }
            lns[i] = leastNumSquares + 1;
        }
        
        return lns[n];
    }

Log in to reply
 

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