Perfect Squares

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k * k <= i; ++k)
                if (dp[i - k * k] != INT_MAX)
                    dp[i] = min(dp[i], dp[i - k * k] + 1);
        return dp[n];
    }
};

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt32
        for k := 1; k*k <= i; k++ {
            if dp[i-k*k] != math.MaxInt32 && dp[i-k*k]+1 < dp[i] {
                dp[i] = dp[i-k*k] + 1
            }
        }
    }
    return dp[n]
}

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            k = 1
            while k * k <= i:
                if dp[i - k * k] + 1 < dp[i]:
                    dp[i] = dp[i - k * k] + 1
                k += 1
        return dp[n]

function numSquares(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let k = 1; k * k <= i; k++) {
            if (dp[i - k * k] + 1 < dp[i]) {
                dp[i] = dp[i - k * k] + 1;
            }
        }
    }
    return dp[n];
}

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k * k <= i; k++) {
                if (dp[i - k * k] != Integer.MAX_VALUE && dp[i - k * k] + 1 < dp[i]) {
                    dp[i] = dp[i - k * k] + 1;
                }
            }
        }
        return dp[n];
    }
}

function numSquares(n: number): number {
    const dp: number[] = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let k = 1; k * k <= i; k++) {
            if (dp[i - k * k] + 1 < dp[i]) {
                dp[i] = dp[i - k * k] + 1;
            }
        }
    }
    return dp[n];
}