Dynamic Programming – Perfect Squares

Find the least number of perfect square numbers (1, 4, 9, 16, 25 …) which sum to the given integer n.

For example, given n = 5, return 2 because 5 = 1 + 4.

Dynamic Programming

The following DP solution has time complexity . The DP recurrence formulas are:

f(i) = min(f(i), f(i - j * j) + 1);
f(0) = 1
f(1) = 1
f(4) = 1
f(9) = 1
...

We use f(n) to represent the minimal required number of the square numbers. And we initialize the f(n) values where n is itself a perfect square number to 1 (obviously). Then we need to check that if there are better (less number) solution exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, INT_MAX);
        int q = (int)sqrt(n);
        for (int i = 0; i <= q; i ++) {
            f[i * i] = 1;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j * j <= i; j ++) {
                f[i] = min(f[i], f[i - j * j] + 1); // better solution by using route i-j*j
            }
        }
        return f[n];
    }
};

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, INT_MAX);
        int q = (int)sqrt(n);
        for (int i = 0; i <= q; i ++) {
            f[i * i] = 1;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j * j <= i; j ++) {
                f[i] = min(f[i], f[i - j * j] + 1); // better solution by using route i-j*j
            }
        }
        return f[n];
    }
};

However, if you know the number theory, you will understand that the answer for any given integers could only be four situations, which is 1, 2, 3, and 4 (at most 4 perfect square numbers). This puzzle can also be solved by using BFS (Breadth First Search) or DFS (Depth First Search) although they might be slower.

To print which perfect squares that sum up to n, we can use the array to remember the path: Find the Least Number Sums of Perfect Squares

–EOF (The Ultimate Computing & Technology Blog) —