据华为数据存储公众号发布，华为公布了2024年奥林帕斯难题悬红。“奥林帕斯奖”（OlympusMons Awards）由华为公司于2019年起设立，奖金100万人民币/个。
华为2024年发布了两个问题，一是每比特极致性价比的存储技术，二是面向AI时代的新型数据底座。两个加起来就是200万，有兴趣的可以挑战一下，机会留给你们，我就不参与了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第279：完全平方数。
问题描述
来源：LeetCode第279题
难度：中等
给你一个整数 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 <= 10^4
问题分析
这题让使用最少的完全平方数，让他们的和等于 n 。我们来把这题转换一下。
给你一个数组nums=[1,2……,sqrt(n)]，从数组中选择任意数字让他们平方的和等于 n ，问所需要的最少数字是多少，并且每个数字没有次数限制。转换 之后我们发现它就是一个完全背包问题。
关于完全背包问题以及代码优化在 中有过详细介绍。不过背包问题求的是最大值，而这里求的是最小值，我们默认每一个数字都给一个最大值，最大值就是全部由 1 的平方组成，代码如下。
JAVA：
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
public int numSquares(int n) {
int sqrt = (int) Math.sqrt(n);
int[] dp = new int[n + 1];
Arrays.fill(dp, n);//dp[i]:和为i的完全平方数的最小数量
dp[0] = 0;
for (int i = 1; i <= sqrt; i++) {// 物品
for (int j = 1; j <= n; j++) {// 背包容量
if (j >= i * i)// 选当前数字和不选当前数字，取最小值
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}C++：
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
public:
int numSquares(int n) {
int sqrtN = (int) sqrt(n);
vector
dp(n + 1, n);//dp[i]:和为i的完全平方数的最小数量 dp[0] = 0; for (int i = 1; i <= sqrtN; i++) {// 物品 for (int j = 1; j <= n; j++) {// 背包容量 if (j >= i * i)// 选当前数字和不选当前数字，取最小值 dp[j] = min(dp[j], dp[j - i * i] + 1); } } return dp[n]; }
C：
// 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
int numSquares(int n) {
int sqrtN = (int) sqrt(n);
int dp[n + 1];
for (int i = 0; i <= n; i++)
dp[i] = n; // dp[i]:和为i的完全平方数的最小数量
dp[0] = 0;
for (int i = 1; i <= sqrtN; i++) {// 物品
for (int j = 1; j <= n; j++) {// 背包容量
if (j >= i * i)// 选当前数字和不选当前数字，取最小值
dp[j] = fmin(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}Python：
# 在nums=[1,2.....sqrt(n)]中选任意数平方和为n的数字
def numSquares(self, n: int) -> int:
sqrt = int(math.sqrt(n))
dp = [n] * (n + 1) # dp[i]:和为i的完全平方数的最小数量
dp[0] = 0
for i in range(1, sqrt + 1): # 物品
for j in range(1, n + 1): # 背包容量
if j >= i * i: # 选当前数字和不选当前数字，取最小值
dp[j] = min(dp[j], dp[j - i * i] + 1)
return dp[n]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。