【力扣100】279.完全平方数 || python中开方表示i**(0.5)

本文主要是介绍【力扣100】279.完全平方数 || python中开方表示i**(0.5)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

添加链接描述
思路：

1. 先设置全是1的可能dp数组；dp[i]表示数值为i的数的可以由最少平方数构成的个数
2. 遍历dp数组，现在数值来到i，那么枚举j，j的范围是[1,开方(i)+1)（左开右闭），因为开方会int全部取整数部分；
3. 我们发现，现在问题变成了dp[i-j*j]最少平方数的个数上，这就是动态规划

class Solution:def numSquares(self, n: int) -> int:res=[i for i in range(n+1)]     #全是1的情况for i in range(2,n+1):for j in range(1,(int(i**(0.5))+1)):res[i]=min(res[i],res[i-j*j]+1)return res[-1]

在力扣（LeetCode）279题中，这个动态规划状态转移方程 dp[i] = min(dp[i], dp[i - j * j] + 1) 是用来求解一个经典的问题，即找出一个正整数 n 能够表示成平方数的最小数量。

让我们解释一下这个状态转移方程：

• dp[i] 表示正整数 i 能够表示成平方数的最小数量。
• dp[i - j * j] 表示如果正整数 i 减去一个平方数 j * j，剩余的数可以被表示成平方数的最小数量。
• 因此，dp[i - j * j] + 1 表示如果我们选择了一个平方数 j * j，则正整数 i 被表示成平方数的数量为 dp[i - j * j] 加上选择的这个平方数 j * j 所贡献的一个数量，因此需要加上 +1。
• 最终，min(dp[i], dp[i - j * j] + 1) 表示我们考虑所有可能的平方数 j * j，选取最小的一个作为正整数 i 的最优解。

通过这个状态转移方程，我们可以逐步计算出正整数 1 到 n 能够表示成平方数的最小数量，最终得到 dp[n] 的值作为结果。

这篇关于【力扣100】279.完全平方数 || python中开方表示i**(0.5)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---