题目

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例

思路

对于给定的整数n，他的完全平方数和可以分成若干个子问题，比如n=12，他的完全平方数和可以分为子问题1和11的完全平方数和或者分为2和10......以此类推，最终我们取最小数目和的子问题方案。

我们用动态规划dp数组来代替这些子问题，dp[0]+dp[11]就代表子问题1和11，以此类推，每次我们都取最小值存入dp数组中，最后取dp[n]表示整数n

代码

/*
*int numSquares(int n)
int numSquares：求整数完全平方数和的最少数量
int n:整数n
返回值：最小数目
*/
int numSquares(int n){
    int dp[n+1];
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        int min = INT_MAX;
        for(int j = 1; j * j <= i; j++)
        {
            min = fmin(min, dp[i - j * j]);
        }
        dp[i] = min + 1;
    }
    return dp[n];
}

时间空间复杂度