给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。 完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是 数据范围:
区块链毕设网qklbishe.com为您提供问题的解答
给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是
数据范围:
import sys def solution(n,m): sq = [i*i for i in range(m+1)] dp = [float("inf") for _ in range(n+1)] dp[0] = 0 for i in range(1,n+1): for j in range(1,m+1): if i<sq[j]:break dp[i] = min(dp[i], dp[i-sq[j]] + 1) return dp[-1] if __name__ == "__main__": n = int(sys.stdin.readline().strip()) sqrt_n = pow(n,0.5) if int(sqrt_n)**2 == n: print("1") else: m = int(sqrt_n) res = solution(n,m) print(res)
52:46
以上就是关于问题给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。 完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1，4，9，和16都是完全平方数，但是2，3，5，8，11等等不是
数据范围:的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}