Problem
We want to find the minimal number of perfect squares we need to add to reach a given integer. For example, 5 needs 2 squares (5 = 1 + 4), 14 needs 3 (14 = 9 + 4 + 1) and 75 needs 3 (75 = 25 + 25 + 25).
Algorithm
This is a typical problem of exploration of a tree of possibilities. It can be tackled by recursion with backtracking, or by dynamic programming.
Let's go the dynamic programming way. In dynamic programming, the principle is to deduce the solution for the current problem from solutions of smaller problems. If the number of smaller problems is not too large, dynamic programming can be quite efficient by computing the solutions of all the smaller problems first.
In our case, finding the minimal number of perfect squares for a target sum can be computed by solving the problem for all the substractions of the target sum by each perfect square, and finding the minimum of these solutions.
For efficiency, we can initialize our solution by the worst sum of squares that we can imagine: a sum of only ones (i.e. 5 = 1 + 1 + 1 + 1 + 1). Also, it is a good idea to avoid using a square root function and the conversion from double to int.
In terms of data structure, we use an array to store at each index the minimum number of perfect square to sum to reach that index. We avoid writing to this array more than once for efficiency.
In our case, finding the minimal number of perfect squares for a target sum can be computed by solving the problem for all the substractions of the target sum by each perfect square, and finding the minimum of these solutions.
For efficiency, we can initialize our solution by the worst sum of squares that we can imagine: a sum of only ones (i.e. 5 = 1 + 1 + 1 + 1 + 1). Also, it is a good idea to avoid using a square root function and the conversion from double to int.
In terms of data structure, we use an array to store at each index the minimum number of perfect square to sum to reach that index. We avoid writing to this array more than once for efficiency.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | public class Solution { public int numSquares(int n) { // Array to find the minimum count for each sum below n. int[] counts = new int[n+1]; // We fill the array from sum = 1 until we reach n. for (int sum = 1; sum <= n; sum++) { // We now compute the minimum number of perfect // squares needed to reach sum. // We know that the worst solution is to use a sum // of ones. int min = sum; // For each sum, we look at which perfect square we // could use to make our count the smallest. // No need to consider ones again, since our initial // value for min, already considers solutions made // of ones. We avoid using the square root function // by directly comparing j ^ 2 to i. for(int j = 2; j * j <= sum; j++){ // Calculate the number of squares to reach i if // we use j * j, and update the current minimum. min = Math.min(counts[sum - j * j] + 1, min); } // Fill the array with the minimum we computed. counts[sum] = min; } return counts[n]; } } |
This problem can be found on career cup and leet code.
