1. Description

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

2. Runtime Distribution

3. Submission Details

4. Example

given n = 12, return 3 because 12 = 4 + 4 + 4;
given n = 13, return 2 because 13 = 4 + 9.

5. Code

import java.util.Arrays;

public class LeetCode0279 {
    public int numSquares(int n) {
        if (n <= 0) {
            return 0;
        }

        int m = (int) Math.sqrt(n);

        long[] dp = new long[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 0; i < dp.length; i++) {
            for (int j = 1; j <= m; j++) {
                int num = j * j;
                if (i + num <= n) {
                    dp[i + num] = Math.min(dp[i + num], dp[i] + 1);
                }
            }
        }
        return (int) dp[n];
    }

    public static void main(String[] args) {
        LeetCode0279 leetcode = new LeetCode0279();
        System.out.println(leetcode.numSquares(13));
    }
}