279. Perfect Squares - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(int(math.sqrt(n)) + 1)]
        
        dp = [float("inf")] * (n+1)
        dp[0] = 0
        
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i-square] + 1)
                
        return dp[-1]

int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i <= n; i++) {
            for (int j = 1; i + j * j <= n; j++) {
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
            }
        }
        return dp[n];
    }