淘宝电商网站怎么做,网站制作教学,哪里有网站建设,轻松seo优化排名题目
279. 完全平方数
中等
相关标签
广度优先搜索 数学 动态规划
给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数#xff0c;其值等于另一个整数的平方#xff1b;换句话说#xff0c;其值等于一个整数自乘的积。例如…题目
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 104
思路和解题方法 在两个版本中都使用了一个一维数组 dp 来保存状态。其中dp[i] 表示当目标数为 i 时需要的最小完全平方数和。初始值为 INT_MAX 表示不可达。在第一个版本中我们通过遍历背包和物品来更新状态。外层循环遍历背包内层循环遍历物品对于每一个背包 i我们尝试将某个完全平方数 j*j 放入背包然后更新状态。递推公式为dp[i] min(dp[i - j * j] 1, dp[i])表示将 j*j 放入背包后需要的完全平方数和为 dp[i - j * j] 1与之前的状态 dp[i] 比较取较小值。而在第二个版本中我们通过遍历物品和背包来更新状态。外层循环遍历物品内层循环遍历背包对于每一个物品 i*i我们尝试将其放入背包 j 中然后更新状态。递推公式为dp[j] min(dp[j - i * i] 1, dp[j])表示将 i*i 放入背包 j 后需要的完全平方数和为 dp[j - i * i] 1与之前的状态 dp[j] 比较取较小值。两个版本的代码实现思路是一样的只是遍历的顺序不同但最终得到的结果是相同的。 复杂度 时间复杂度: O(n * sqrt(n)) sqrt()为开方函数 时间复杂度 两个版本的代码都使用了嵌套循环。最外层的循环遍历的次数都是目标数 n内层的循环遍历的次数都是完全平方数的个数而最大的完全平方数为 sqrt(n)因此内层循环的时间复杂度为 O(sqrt(n))。因此两个版本的代码的时间复杂度都是 O(n * sqrt(n))。 空间复杂度 O(n) 空间复杂度 两个版本的代码都使用了一个一维数组 dp 来记录状态。数组的长度为 n 1因此空间复杂度为 O(n)。而其他变量的空间复杂度都是常数级别的。 c 代码
// 版本一
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX); // 创建一个大小为 n1 的数组初始化为 INT_MAX表示不可达状态dp[0] 0; // 初始条件当目标数为 0 时需要的最小完全平方数和为 0for (int i 0; i n; i) { // 遍历背包i 表示当前目标数for (int j 1; j * j i; j) { // 遍历物品j*j 表示完全平方数dp[i] min(dp[i - j * j] 1, dp[i]); // 更新状态取较小值}}return dp[n]; // 返回目标数为 n 时的最小完全平方数和}
};// 版本二
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX); // 创建一个大小为 n1 的数组初始化为 INT_MAX表示不可达状态dp[0] 0; // 初始条件当目标数为 0 时需要的最小完全平方数和为 0for (int i 1; i * i n; i) { // 遍历物品i 表示当前物品即完全平方数for (int j i * i; j n; j) { // 遍历背包j 表示当前目标数dp[j] min(dp[j - i * i] 1, dp[j]); // 更新状态取较小值}}return dp[n]; // 返回目标数为 n 时的最小完全平方数和}
};Java代码
class Solution {// 版本一先遍历物品, 再遍历背包public int numSquares(int n) {int max Integer.MAX_VALUE;int[] dp new int[n 1];// 初始化for (int j 0; j n; j) {dp[j] max;}// 当和为0时组合的个数为0dp[0] 0;// 遍历物品for (int i 1; i * i n; i) {// 遍历背包for (int j i * i; j n; j) {// 更新状态取较小值dp[j] Math.min(dp[j], dp[j - i * i] 1);// 不需要这个if判断语句因为在完全平方数这一问题中不会有凑不成的情况发生一定可以用1来组成任何一个n所以注释掉了这个if语句。}}return dp[n]; // 返回目标数为 n 时的最小完全平方数和}
}class Solution {// 版本二 先遍历背包, 再遍历物品public int numSquares(int n) {int max Integer.MAX_VALUE;int[] dp new int[n 1];// 初始化for (int j 0; j n; j) {dp[j] max;}// 当和为0时组合的个数为0dp[0] 0;// 遍历背包for (int j 1; j n; j) {// 遍历物品for (int i 1; i * i j; i) {// 更新状态取较小值dp[j] Math.min(dp[j], dp[j - i * i] 1);}}return dp[n]; // 返回目标数为 n 时的最小完全平方数和}
}觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
