Simple java dp solution


  • 0
    F
    • first, create an array of length n
    • iterate the array, we partition the array into [0,1),[1,4),[4,9),...[i*i,(i+1)*(i+1)),... and iterate on them
    • for perfect squares, we let it be 1, otherwise, dp[x+k*k]=min(dp[x+k*k],dp[x]+1)
    public int numSquares(int n) {
            int[] dp = new int[n];
            Arrays.fill(dp, 4);
            for (int i = 1; i * i <= n; i++) {
                dp[i * i - 1] = 1;
                for (int j = i * i; j < Math.min(n, i * i + 2 * i); j++) {
                    for (int k = 1; k <= i; k++) {
                        dp[j] = Math.min(dp[j], dp[j - k * k] + 1);
                    }
                }
            }
            return dp[n - 1];
        }

Log in to reply
 

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