LeetCode 279. Perfect Squares

perfect-squares.java

/**
 * https://leetcode.com/problems/perfect-squares/
 *
 * O(n ^ 1.5) runtime, O(n) space
 *
 * use DP to solve this question
 */

public class Solution {
    public int numSquares(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        int[] nums = new int[n+1];
        nums[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (isPerfectSquare(i)) {
                nums[i] = 1;
            } else {
                nums[i] = i; // i = 1 + ... + 1
                
                // the largest perfect square number could be used is ((int) Math.sqrt(i)) ^ 2
                for (int j = (int) Math.sqrt(i); j >= 2; j--) { // j = 1 could be skipped here
                    int t = 1 + nums[i-j*j]; // note that nums[j*j] is 1, because it's a perfect square number
                    nums[i] = Math.min(nums[i], t);
                }
            }
        }
        return nums[n];
    }
    
    // verify n is a perfect square number
    private boolean isPerfectSquare(int n) {
        int root = (int) Math.sqrt(n); // note (int) here
        return n == root * root;
    }
}