神刀安全网

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 Dynamic Programming – Perfect Squares

. 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

loading…

298 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Dynamic Programming – Perfect Squares

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址