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 = 12
- Output: 3
- Explanation: 12 = 4 + 4 + 4.
- Example 2:
- Input: n = 13
- Output: 2
- Explanation: 13 = 4 + 9.
思路: dp[i] 表示和为 i 的最少的完全平方数个数.
- class Solution {
- public:
- int numSquares(int n) {
- if (n <= 0)
- return 0;
- vector<int> dp(n + 1, 0);
- dp[0] = 0;
- for (int i = 1; i <= n; i++) {
- dp[i] = INT_MAX;
- for (int j = 1; j * j <= i; j++) {
- dp[i] = min(dp[i], dp[i - j * j] + 1);
- }
- }
- return dp[n];
- }
- };
- static dynamic programming:
- class Solution {
- public:
- int numSquares(int n) {
- if (n <= 0)
- return 0;
- static vector<int> dp({0});
- while (dp.size() <= n) {
- int m = dp.size();
- int cnt = INT_MAX;
- for (int j = 1; j * j <= m; j++) {
- cnt = min(cnt, dp[m - j * j] + 1);
- }
- dp.push_back(cnt);
- }
- return dp[n];
- }
- };
思路三: 数学方法: 勒让德多项式.
来源: http://www.bubuko.com/infodetail-3195434.html