每日一题：完全平方数

赞

题目279：完全平方数


给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例1：

输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4.
示例2：
输入: n = 13输出: 2解释: 13 = 4 + 9.
分析

动态规划问题，我是首先手动列出来前几个数字的输入输出：

输入 输出 解释n=1,  1,    1n=2,  2,    1,1n=3,  3,    1,1,1n=4,  1,    4n=5,  2,    4,1n=6,  3,    4,1,1n=7,  4,    4,1,1,1n=8,  2,    4,4n=9,  1,    9
这里大概就可以看出规律了吧，用dp[i]表示和为i的完全平方和的个数，有
dp[0]=0;dp[i]=min(dp[i-i之前的完全平方和]+1);
代码：
class Solution {public:    int numSquares(int n) {        vector<int> dp(n+1, INT_MAX);        dp[0] = 0;        for (int i = 1; i <=n; ++i) {            // 使用tem少进行一次乘法运算            for (int j = 1, tem = 0; tem = j * j, tem <= i; ++j) {                 dp[i] = min(dp[i], dp[i-tem] + 1);            }        }        return dp[n];    }};