Posts Perfect Squares
Post
Cancel

Perfect Squares

Problem Description

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

leetcode

Solution

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    public int numSquares(int n) {
        
        int[] dp = new int[n+1];
        dp[0] = 0;

        for(int i=1; i<=n; i++){

            int ans=i; //If we take all 1s
            for(int j=1; j*j<=i; j++){
                ans = Math.min(ans, 1 + dp[i-(j*j)]);
            }

            dp[i] = ans;

        }

        return dp[n];

    }
}
This post is licensed under CC BY 4.0 by the author.