[LeetCode] 279. Perfect Squares

 Problem : https://leetcode.com/problems/perfect-squares/

I know there is a much better solution. But this memorization approach is easy to understand for me.

class Solution {
    HashMap<Integer, Integer> memo = new HashMap();
    
    {
        memo.put(0, 0);
    }
    
    public int numSquares(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int result = Integer.MAX_VALUE;
        
        for (int x = 1; x * x <= n; x++) {   
            result = Math.min(result, 1 + numSquares(n - x*x));
        } 
        
        memo.put(n, result);
        return result;
    }
}

A buttom-up solution:

class Solution:
    def numSquares(self, n: int) -> int:
        INT_MAX = 2**31 - 1
        
        dp = [INT_MAX] * (n+1)
        dp[0] = 0
        
        i = 1
        while i * i < n:
            dp[i*i] = 1
            i += 1
        
        for i in range(1, n+1):
            if dp[i] != INT_MAX: continue
                
            for j in range(1, int(math.sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

Edited on 12/02/2021. Update the top-down solution.