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.
Solution 1: DP
dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i
dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};
dp[5] = 2
Time complexity: O(n * sqrt(n))
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, running time: 104 ms class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX >> 1); dp[0] = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j * j <= i; ++j) dp[i] = min(dp[i], dp[i - j * j] + 1); return dp[n]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment