每一个正整数 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])

相关问题

用Java写一个程序，每个数均可表示成若干完全平方数(1,4,9,16,25…)之和，完全平方数是可重复，求出n的一种组合要求完全平方数的个数最少。 如：12 = 4 + 4 + 4; 13 = 4 + 9

好的，我可以为您提供一个 Java 程序，来实现这个功能。程序使用了动态规划的思想，具体实现如下：

import java.util.Arrays;
import java.util.Scanner;

public class MinSquareCount {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入一个正整数：");
        int n = scanner.nextInt();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        System.out.println("需要的最少完全平方数个数为：" + dp[n]);
    }
}

程序中，使用了一个长度为 n+1 的数组 dp 来记录每个数需要的最少完全平方数个数。初始化时，将 dp 数组中每个元素都赋为 Integer.MAX_VALUE，表示这个数目前还不可达。

然后，程序从 1 循环到 n，对于每个数，再从 1 循环到它的平方根，枚举每个可能的完全平方数，计算出它所需要的最少完全平方数个数，更新 dp 数组。

最后输出 dp[n]，即为需要的最少完全平方数个数。

例如，当输入 12 时，程序会输出 3，即 12 可以表示为 4+4+4 的形式，需要的完全平方数个数为 3。