题目描述
题目链接:279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
1
,4
,9
,16
, …) which sum to n.
例子
例子 1
Input:
n = 12
Output:3
Explanation:12 = 4 + 4 + 4
例子 2
Input:
n = 13
Output:2
Explanation:13 = 4 + 9
解题思路
这道题可能一下子想不到用动态规划来做。但是如果如果我们把 (1 ~ n) 中任意一个数看成 n = a + b;那么就可以求解 min_nums(n) = min_nums(a) + min_nums(b),因此我们只要遍历所有的相加组合,进行最小化更新即可。而在这其中,由于要考虑的是平方数相加,所以我们只需要更新包括平方数相加的组合,具体如下:
1 |
|
- 时间复杂度: O(n*sqrt(n))
- 空间复杂度: O(n)
GitHub 代码同步地址: 279.PerfectSquares.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions