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 =12Output: 3 Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13Output: 2 Explanation:13 = 4 + 9.
思路：dp[i]表示和为i的最少的完全平方数个数。
1 class Solution { 2 public: 3 int numSquares(int n) { 4 if (n <= 0) 5 return 0; 6 vector<int> dp(n + 1, 0); 7 dp[0] = 0; 8 for (int i = 1; i <= n; i++) { 9 dp[i] = INT_MAX; 10 for (int j = 1; j * j <= i; j++) { 11 dp[i] = min(dp[i], dp[i - j * j] + 1); 12 } 13 } 14 return dp[n]; 15 } 16 };
static dynamic programming:
1 class Solution { 2 public: 3 int numSquares(int n) { 4 if (n <= 0) 5 return 0; 6 static vector<int> dp({0}); 7 while (dp.size() <= n) { 8 int m = dp.size(); 9 int cnt = INT_MAX; 10 for (int j = 1; j * j <= m; j++) { 11 cnt = min(cnt, dp[m - j * j] + 1); 12 } 13 dp.push_back(cnt); 14 } 15 return dp[n]; 16 } 17 };
思路三：数学方法：勒让德多项式。
原文：https://www.cnblogs.com/qinduanyinghua/p/11515706.html