Leetcode Perfect Squares problem solution

In this Leetcode Perfect Squares problem solution, we have 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.

Problem solution in Python.

class Solution(object):
    def numSquares(self, n):
        from math import ceil, sqrt
        dp = [0, 1, 2, 3]
        if n<=3:
            return dp[n]
        else:
            for i in range(4, n + 1):
                dp.append(i)
                for x in range(1, int(ceil(sqrt(i))) + 1):
                    temp = x*x
                    if temp>i:
                        break
                    else:
                        dp[i] = min(dp[i], 1 + dp[i - temp])
        return dp[n]

Problem solution in Java.

class Solution {
    public int numSquares(int n) {
        int sqrtN = (int) Math.sqrt(n);
        int[] squares = new int [sqrtN];
        for (int i = 1; i <= sqrtN; i++) {
            squares[i - 1] = i * i;
        }
        int[] dp = new int [n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = n + 1;
            for (int j = 0; j < squares.length; j++) {
                if (i < squares[j]) {
                    continue;
                }
                if (squares[j] == i) {
                    dp[i] = 1;
                    continue;
                } else {
                    dp[i] = Math.min(dp[i], 1 + dp[i - squares[j]]);
                }
            }
        }
        return dp[n];
    }
}

Problem solution in C++.

class Solution {
public:
    int numSquares(int n)
    {
        if (n==0) return 0;
        vector<int> per;
        int f[n+5]={0};
        f[1]=1;
        for(int i=2;i<=n;i++)
        {
            int minV=INT_MAX;
            int j=1;
            while (j*j<=i)
            {
                if (j*j==i)
                {
                    minV=1;break;
                }
                minV=min(minV,f[i-j*j]+1);
                j++;
            }
            f[i]=minV;
        }
        return f[n];
    }
};

Problem solution in C.

void solve(int n, int * ans, int a){
    if (a > *ans) return;
    if (n == 0) {
        if (a < *ans) *ans = a;
        return; 
    }
    
    int z = 1;
    
    while (z++) { 
        // Find the biggest perfect square that is less than n.
        if (z*z > n) {
            z = z-1;
            break;
        }
    }

    while (z > 0) {
        // Start with the biggest perfect square less than n and
        // continue trying every perfect square less than that.
        solve(n - z*z, ans, a+1);
        if (a+2 >= *ans) break;
        z = z-1;
    } 

    return; 
}   

int numSquares(int n) {
    int ans = INT_MAX;
    solve(n, &ans, 0);
    return ans;
}

coding problems