279. Perfect Squares (Medium)
https://leetcode.com/problems/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.
Example 1:
Input: n =12
Output: 3 Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13
Output: 2 Explanation:13 = 4 + 9.
Solutions
class Solution {
// This problem is pretty much similar with 322. Coin Change. When it comes to
// exchanges, the squares 1, 4, 9, 16 can be perfectly regarded as the coin denominations.
public int numSquares(int n) {
int x = (int) Math.sqrt(n);
int[] squares = new int[x];
for (int i = 1; i <= x; i++) {
squares[i - 1] = i * i;
}
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < x; j++) {
if (i - squares[j] < 0) {
continue;
}
dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
}
}
return dp[n];
}
}