[LeetCode] 279、完全平方数

题目描述给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, …使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例输入:n12输出:3解释:12444.解题思路开始根本看不出来这是一个“动态规划”题目蓝瘦。动态规划创建一个长度为n1的数组dp[i]表示数字i最少可以由几个平方数构成初始化dp[i]i比如i4最坏结果为11114即为4个数字动态转移方程为dp[i] min(dp[i], dp[i - j * j] 1)i表示当前数字j*j表示平方数。其中j的遍历区间为for (int j 1; j * j i; j)。时间复杂度O(nn)O(n\sqrt{n})O(nn​)。参考代码classSolution{public:intnumSquares(intn){if(n1){returnn;}vectorintdp(n1,INT_MAX);// 应该迭代法初始化dp[i]idp[0]0;// 注意这个是0dp[1]1;for(inti2;in;i){for(intj1;j*ji;j){// 这里必须是因为n可能本身就是个完全平方数dp[i]min(dp[i],dp[i-j*j]1);// 别忘 1}}returndp[n];}};