Perfect Squares - Lintcode

Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum to n.

Example

Given n =12, return3because12 = 4 + 4 + 4
Given n =13, return2because13 = 4 + 9

Analysis

First of all, we know that the answer for perfect square number, such as 1, 4, 9, 16, is 1. We also know that the answer of n, when n is not a perfect square number, is min(ps(n-1) + 1, ps(n-psnumber) + 1).

Solution

public int numSquares(int n) {
    int[] result = new int[n + 1];
    Arrays.fill(result, Integer.MAX_VALUE);

    for (int i = 0; i * i <= n; i++){
        result[i * i] = 1;   
    }

    for (int i = 0; i <= n; i++){
        for (int j = 1; j * j <= i; j++){
            result[i] = Math.min(result[i], result[i - j * j] + 1);
        }
    }

    return result[n];
}