Perfect Squares

LeetCode Q 279 - Perfect Squares

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

Solution

DP function:
dp[n] = Min{ dp[n - i*i] + 1 }, n - i*i >=0 && i >= 1

Code:

public int numSquares(int n) {
	int[] dp = new int[n + 1];
	Arrays.fill(dp, Integer.MAX_VALUE);
	for (int i = 0; i * i <= n; i++) 
		dp[i * i] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j * j <= i; j++) {
			dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
		}
	}
	return dp[n];
}