C语言重构【279】完全平方数

男娘i 2022-11-09 01:27 49阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
    
    给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
    
    完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
    
     
    
    示例 1：
    
    输入：n = 12
    输出：3 
    解释：12 = 4 + 4 + 4
    示例 2：
    
    输入：n = 13
    输出：2
    解释：13 = 4 + 9
     
    提示：
    1 <= n <= 104

#### 方案： ####

class Solution
    { 
    public:
        int numSquares(int n)
        { 
            if (n < 4)
                return n;
            vector<int> dp(n + 1, 0);
            //初始化为最坏的情况
            for (int i = 1; i <= n; i++)
            { 
                dp[i] = i;
            }
            vector<int> sqnum(n, 0);
            //初始化平方数
            int k = 1;
            while (sqnum[k - 1] <= n)
            { 
                sqnum[k] = k * k;
                k++;
            }
    
            for (int i = 4; i <= n; i++)
            { 
                k = 1;
                while (sqnum[k] <= i)
                { 
                    dp[i] = min(dp[i - sqnum[k++]] + 1, dp[i]);
                }
            }
            return dp[n];
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n^1.5)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode