Perfect Squares — Coin Change with Squares

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

from collections import deque
class Solution:
    def numSquares(self, n: int) -> int:
        squares=[i*i for i in range(1,int(n**0.5)+1)]
        q=deque([n]); visited={n}; level=0
        while q:
            level+=1
            for _ in range(len(q)):
                rem=q.popleft()
                for sq in squares:
                    nxt=rem-sq
                    if nxt==0: return level
                    if nxt>0 and nxt not in visited: visited.add(nxt); q.append(nxt)
        return level

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 j=1;j*j<=i;j++) dp[i]=min(dp[i],dp[i-j*j]+1);
        return dp[n];
    }
};