首页 > 其他分享 >279. 完全平方数

279. 完全平方数

时间:2024-05-17 11:30:04浏览次数:19  
标签:平方 int 整数 完全 jj 279 dp

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

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

示例 1:

输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

class Solution {
public:
    int numSquares(int n) {
        vector<int>dp(n+1,n);
        dp[0]=0;
        for(int i=1;i<n+1;i++)
        {
            for(int j=0;j*j<=i;j++){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];

    }

};

创建一个长度为 n+1 的向量 dp,其中 dp[i] 表示和为 i 的最小完全平方数个数。

首先将 dp 向量初始化为 n,因为任何正整数都可以表示为至多 n 个完全平方数之和。然后我们将 dp[0] 设为 0,因为 0 的最小完全平方数个数为 0。

接下来,遍历从 1 到 n 的所有整数。对于每个整数 i,找到所有小于或等于 i 的完全平方数 j^2,并更新 dp[i] 为 dp[i] 和 dp[i - jj] + 1 中的较小值。这是因为如果我们可以用 dp[i - jj] 个完全平方数表示 i - jj,那么我们只需要再加一个 jj(也就是dp[i-j*j]+1) 就可以表示 i。

最终,我们返回 dp[n],即和为 n 的最小完全平方数个数。

标签:平方,int,整数,完全,jj,279,dp
From: https://www.cnblogs.com/donghao99/p/18197527

相关文章

  • 《Linux内核完全注释》学习笔记:2.3 Linux系统定时
    在Linux0.11内核中,PC的可编程定时芯片Intel8253被设置成每隔10ms就发出一个时钟中断(IRQ0)信号。这个时间节拍就是系统运行的脉搏,我们称之为1个系统滴答。因此每经过1个滴答就会调用一次时钟中断处理程序(timer_interrupt)。该处理程序主要用来通过jiffies变量来累计自......
  • 《Linux内核完全注释》学习笔记:2.1 Linux内核模式和体系结构
    2.1Linux内核模式和体系结构操作系统主要由4部分组成:硬件、操作系统内核、操作系统服务用户应用程序图2-1操作系统组成部分用户应用程序:指那些字处理程序、互联网浏览器程序或用户自行编制的各种应用程序;操作系统服务程序:指向用户提供的服务,被看作是操作系统部分功能......
  • 《Linux内核完全注释》学习笔记:2.2 Linux中断机制
    在使用80x86组成的PC中,采用了两片8259A可编程中断控制芯片。每片可以管理8个中断源。通过多片的级联方式,能构成最多管理64个中断向量的系统。在PC/AT系列兼容机中,使用了两片8259A芯片,共可管理15级中断向量。其级联示意图见图2-5。其中从芯片的INT引脚连接到主芯片的IR2引......
  • 使用 Playwright 脚本录制简化自动化测试:完全指南
    前言自动化测试是软件开发中的重要环节,它可以提高测试效率和代码质量。然而,编写自动化测试脚本可能需要花费大量时间和精力。为了简化这一过程,Playwright提供了一个强大的功能,称为脚本录制,它可以帮助开发人员通过交互式操作自动生成测试脚本。本文将深入介绍如何使用Playwrigh......
  • 解锁弹框:Python 下的 Playwright 弹框处理完全指南
    前言在Web自动化测试中,处理弹框是一项常见的任务。弹框可能包括警告、确认和提示框。Playwright是一个功能强大的自动化测试工具,提供了处理这些弹框的灵活方法。在本文中,我们将深入探讨如何使用Python编写代码来处理各种类型的弹框。弹框的分类弹框通常分为3种,分别为aler......
  • 完全开源可商用!一个简洁、高效、安全的快速开发平台!
    大家好,我是Java陈序员。问君能有几多愁,开源项目解千愁!今天,给大家介绍一个快速开发平台,完全开源可商用!关注微信公众号:【Java陈序员】,获取开源项目分享、AI副业分享、超200本经典计算机电子书籍等。项目介绍SmartAdmin——一个简洁、高效、安全的快速开发平台,以高质量代码......
  • AI回答总不满意?你的提问方式可能完全错误!
    AI回答总不满意?你的提问方式可能完全错误!大家好,我是卷福同学,一个专注AI大模型整活的前阿里程序员,腾讯云社区2023新秀突破作者向AI提问想写一篇论文,结果AI就生成2000字左右的文章后就完了。小伙伴们是不是也会遇到这类情况呢。今天来教大家AI提示词的技巧,学会向AI提问。Prompt......
  • 跟着ChatGPT学算法-完全背包问题
    一、题目给定n个物品,第i个物品的重量为wgt[i-1]、价值为val[i-1],和一个容量为cap的背包。每个物品可以重复选取,问在限定背包容量下能放入物品的最大价值。 二、和ChatGPT聊聊您您是一位资深算法工程师,请深入浅出地给出完全背包问题的分析过程和完整带注释的Java代......
  • StarCoder2-Instruct: 完全透明和可自我对齐的代码生成
    指令微调是一种技术,它能让大语言模型(LLMs)更好地理解和遵循人类的指令。但是,在编程任务中,大多数模型的微调都是基于人类编写的指令(这需要很高的成本)或者是由大型专有LLMs生成的指令(可能不允许使用)。我们推出了一个叫做StarCoder2-15B-Instruct-v0.1的模型,这是第......
  • 代码随想录训练营第二天 | 977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II
    977.有序数组的平方题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/文章讲解:https://programmercarl.com/0977.有序数组的平方.html视频讲解:https://www.bilibili.com/video/BV1QB4y1D7ep暴力解时间复杂度O(nlogn)空间复杂度O(1)双指针法时间复......