LeetCode-279. Perfect Squares

LeetCode-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.

Example 1:

Input: n =

12

Output: 3

Explanation:

12 = 4 + 4 + 4.

Example 2:

Input: n =

13

Output: 2

Explanation:

13 = 4 + 9.

题解：

dp问题，每次更新加入新元素后每个数需要的最小个数。

class Solution {public: int numSquares(int n) { int k = sqrt(n); vector dp; for (int i = 0; i <= n; i++) { dp.push_back(i); } for (int i = 1; i <= k; i++) { for (int j = i * i; j <= n; j++) { dp[j] = min(dp[j], 1 + dp[j - i * i]); } } return dp[n]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。