Python如何计算一个正整数n所需的最少完全平方数个数？

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

目录

1.题目描述

2.代码实现

3.运行结果

1. 题目描述

给定一个正整数n，请找出最少的完全平方数，使得它们的和等于n。

2. 代码实现pythondef find_min_squares(n): # 动态规划表，dp[i]表示组成i的最小完全平方数个数 dp=[float('inf')] * (n + 1) dp[0]=0 # 0个完全平方数的和为0

# 遍历所有可能的完全平方数 for i in range(1, n + 1): j=1 while j * j <=i: dp[i]=min(dp[i], dp[i - j * j] + 1) j +=1

return dp[n]

测试n=12print(find_min_squares(n))

3. 运行结果

3

目录

​​1、题目描述​​

​​2、代码实现​​

​​3、运行结果​​

---

1、题目描述

给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9... )的和等于 n。