如何用Python实现LeetCode 279题的完全平方数查找算法？

本文共计492个文字，预计阅读时间需要2分钟。

【题目描述】给你一个整数n，返回和为n的最小平方数个数。

【题目解析】完全平方数是一个整数可以表示为某个整数的平方。例如，1, 4, 9, 16等都是完全平方数。题目要求找出所有和为n的最小平方数个数。

【代码实现】pythondef min_squares(n): dp=[0] * (n + 1) for i in range(1, n + 1): dp[i]=float('inf') for j in range(1, int(i ** 0.5) + 1): dp[i]=min(dp[i], dp[i - j * j] + 1) return dp[n]

示例n=12result=min_squares(n)print(result) # 输出结果

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

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