给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16 都是完全平方数，而 3和 11 不是。
一个整数 n
一个整数表示和为 n 的完全平方数的最少数量
输入
12
输出
3
12=4+4+4
输入
13
输出
2
13=4+9
提示：
给定一个整数 n，要求返回和为 n 的完全平方数的最少数量。
完全平方数 指的是形如 k2 的数，其中 k 为整数。例如，1、4、9、16 均为完全平方数，而 3 和 11 不是。
本题可以使用动态规划（DP）解决。定义一个数组 dp，其中 dp[i] 表示和为 i 的完全平方数的最少数量。
状态转移：
对于每个 i，遍历所有满足 j2≤i 的 j，更新公式为
其中 dp[i−j2]+1 表示在和为 i−j2 的解的基础上再加上一个 j2。
初始状态：
dp[0]=0，表示数字 0不需要任何完全平方数的和即可表示。
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;
// 使用 Solution 类封装功能函数
class Solution {
public:
// 函数 numSquares 求解和为 n 的完全平方数的最少数量
int numSquares(int n) {
// dp 数组，dp[i] 表示和为 i 的最少完全平方数数量
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0; // 当 i=0 时，数量为 0
// 遍历每个数字 i
for (int i = 1; i <= n; i++) {
// 枚举所有可能的完全平方数 j^2
for (int j = 1; j * j <= i; j++) {
// 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
};
int main() {
int n;
// 输入整数 n
cin >> n;
Solution sol;
// 输出结果
cout << sol.numSquares(n);
return 0;
}
# 定义 Solution 类封装功能函数
class Solution:
# 函数 numSquares 求解和为 n 的完全平方数的最少数量
def numSquares(self, n: int) -> int:
# dp 数组，dp[i] 表示和为 i 的最少完全平方数数量
dp = [float('inf')] * (n + 1)
dp[0] = 0 # 当 i=0 时，数量为 0
# 遍历每个数字 i
for i in range(1, n + 1):
j = 1
# 枚举所有可能的完全平方数 j^2
while j * j <= i:
# 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
dp[i] = min(dp[i], dp[i - j * j] + 1)
j += 1
return dp[n]
if __name__ == '__main__':
# 输入整数 n
n = int(input())
sol = Solution()
# 输出结果
print(sol.numSquares(n))
import java.util.Scanner;
public class Main {
// 使用 Solution 类封装功能函数，符合 leetcode 风格
static class Solution {
// 函数 numSquares 求解和为 $n$ 的完全平方数的最少数量
public int numSquares(int n) {
// dp 数组，dp[i] 表示和为 $i$ 的最少完全平方数数量
int[] dp = new int[n + 1];
// 初始化 dp 数组，除 dp[0] 外均设为较大值
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
// 枚举所有可能的完全平方数 j^2
for (int j = 1; j * j <= i; j++) {
// 状态转移方程：dp[i] = min(dp[i], dp[i - j^2] + 1)
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入整数 n
int n = sc.nextInt();
Solution sol = new Solution();
// 输出结果
System.out.println(sol.numSquares(n));
}
}