输入一个正整数 n ，输出和为 n 的完全平方数（1,4,9,16......）的最少数量 。例如n=12，n = 4+4+4，所以结果为3；n = 13，n = 4+9，结果为2。

这是一个经典的数学问题，可以使用动态规划来解决。具体地，我们定义一个一维数组 dp，其中 dp[i] 表示和为 i 的完全平方数的最小数量。

状态转移方程为：

dp[i] = min(dp[i-j*j]+1)，其中 j*j <= i。

也就是说，我们枚举所有小于等于 i 的完全平方数 j*j，然后将 dp[i-j*j] 的值加 1，即可得到 dp[i] 的值。

最终的答案即为 dp[n]。下面是 Python 代码实现：

def numSquares(n: int) -> int:
    dp = [float('inf')] * (n+1)  # 初始化为正无穷
    dp[0] = 0  # 定义初始状态
    for i in range(1, n+1):
        for j in range(1, int(i**0.5)+1):
            dp[i] = min(dp[i], dp[i-j*j]+1)
    return dp[n]

测试一下：

>>> numSquares(12)
3
>>> numSquares(13)
2

因为时间复杂度为 $O(n\sqrt{n})$，所以对于较大的 n，运行时间可能会比较长。但是在 n 不太大的情况下，这个算法是可行的。

相关问题

java输入一个正整数 n ，输出和为 n 的完全平方数（1,4,9,16......）的最少数量 。例如n=12，n = 4+4+4，所以结果为3；n = 13，n = 4+9，结果为2。

这个问题可以使用动态规划算法来解决。假设我们已经知道了对于所有小于n的正整数，它们的最少完全平方数数量，我们可以用这些结果来计算n的结果。

我们可以定义一个长度为n+1的数组dp，其中dp[i]表示和为i的完全平方数的最少数量。显然，dp[0]=0，因为和为0的完全平方数数量为0。对于其他的i，我们可以通过以下方式来计算dp[i]：

1.初始化dp[i]为i，这是最坏情况下的答案，即由i个1组成。

2.遍历所有小于等于i的完全平方数j，计算dp[i-j*j]+1的值，并将其与当前的dp[i]比较。如果dp[i-j*j]+1小于dp[i]，则更新dp[i]的值。

3.返回dp[n]作为答案。

下面是Java代码实现：

public static int getMinSquareNum(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

测试：

public static void main(String[] args) {
    System.out.println(getMinSquareNum(12));  // 输出3
    System.out.println(getMinSquareNum(13));  // 输出2
}

每一个正整数 n 都可以写成若干个完全平方数之和。例如 12=4+4+4。输入 正整数 n，计算 n 最少可以表示成几个完全平方数之和。

这是一个经典的数学问题，称为“四平方和定理”。

根据四平方和定理，任何一个正整数都可以表示成不超过四个完全平方数之和。

因此，我们可以先尝试将 n 表示成一个完全平方数，如果不能，则尝试将 n 表示成两个完全平方数之和，如果还是不能，则尝试将 n 表示成三个完全平方数之和，最后如果还是不能，则 n 可以表示成四个完全平方数之和。

具体实现可以使用动态规划算法，定义状态 dp[i] 表示将 i 表示成完全平方数之和的最小个数。转移方程为：

dp[i] = min(dp[i], dp[i-j*j]+1)

其中 j*j 是一个完全平方数，i-j*j 是剩余部分，dp[i-j*j]+1 表示将剩余部分表示成完全平方数之和的最小个数加上 j*j 这个完全平方数。

最终的答案即为 dp[n]。

以下是 Python 代码实现：

import math

n = int(input())

# 初始化 dp 数组
dp = [float('inf')] * (n+1)
dp[0] = 0

# 动态规划
for i in range(1, n+1):
    for j in range(1, int(math.sqrt(i))+1):
        dp[i] = min(dp[i], dp[i-j*j]+1)

# 输出结果
print(dp[n])