# 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 followingDP 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 ...`
`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.

`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 thenumber 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.

–EOF–

GD Star Rating