58ms Java DP solution beating over 90%


  • 15
    L
    public class Solution {
    /**
     * s[i] denotes the least number of square numbers that add up to n
     * initial s[i] as maximum integer
     * for i from 1 to n, 
     *      if i is perfect square, s[i]=1, 
     *      otherwise get the square root of the maximum perfect square smaller than i
     * for j from 1 to square root, 
     *      if(s[i-j*j]+1<s[i]) update s[i] as s[i-j*j]+1
     * 
     * */
    public int numSquares(int n) {
        int[] s = new int[n+1];
        for(int i=0;i<n+1;i++) s[i] = Integer.MAX_VALUE;
        //note to me: no need to store a list of perfect squares, knowing the square root of the largest perfect square is sufficient
        //List<Integer> squares = new ArrayList<Integer>();
        for(int i = 1;i<n+1;i++){
            int sqrt = (int) Math.sqrt(i);
            if(i == sqrt*sqrt){s[i] = 1;continue;}
            for(int j = 1;j<=sqrt;j++){
                if(s[i-j*j]+1<s[i]) s[i] = s[i-j*j]+1;
            }
        }
        return s[n];
    }
    

    }


  • 0
    H

    How to guarantee the minimum only comes from s[i-j*j], for int j = 1;j<=sqrt;j++?


  • 0
    L

    The trick is s[i-j*j]+1. Because for every square number, the best case is that the existing sum plus the square number exactly once could result to n, right? For example, say you want to calculate the least number of square numbers adding up to 10 (s[10]). All the square numbers less than 10 are 1,4,9. And you already know the values of s[1] to s[9]. For 1, the best case should be 9 plus 1. The least number of square numbers adding up to 9 (s[9]) is 1, so s[10] is temporarily s[9]+1. Similarly, for 4, the best case should be 6 plus 4. You find the least number of square numbers adding up to 6 (s[6]) and plus 1. If it's smaller than s[9]+1, assign s[10] to s[6]+1. Same logic applies to 9...


Log in to reply
 

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