279. Perfect Squares.md

279. Perfect Squares

Tag

• 1D DP
• Amazon, Microsoft

Description

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.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution

1D bottom-up DP

• This is similar to 322. Coin Change, 1 dimension DP solution, where each state has [valid perfect square #] of dependent states

class Solution {
    public int numSquares(int n) {
        // Calculate all possible perfect squares
      	int[] squareNum = getSquare(n);
        // Create a dp memo
        int[] memo = new int[n + 1]; // memo[i]: min # of perfect squares sum up to i
        Arrays.fill(memo, n + 1);
        // Base case
        memo[0] = 0;        
        
        // DP
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < squareNum.length; j++) {
                if (squareNum[j] <= i) {
                    memo[i] = Math.min(memo[i], memo[i - squareNum[j]] + 1);
                }
            }
        }
        
        return memo[n]; 
    }
  
  	private int[] getSquare(int n) {
      	int maxIdx = (int) Math.sqrt(n);
        int[] squareNum = new int[maxIdx + 1]; // Store perfect square values (one extra space for 0)
        for (int i = 1; i <= maxIdx; i++) {
            squareNum[i] = i * i;
        }
      	
      	return squareNum;
    }
}

• TC: O(n * \sqrt n)

• SC: O(n)