当前位置: 首页 > news >正文

力扣279. 完全平方数

Problem: 279. 完全平方数

文章目录

  • 题目描述
  • 思路及解法
  • 复杂度
  • Code

题目描述

在这里插入图片描述

思路及解法

1.定义一个int数组dp初始化长度为n+1;
2.状态初始化:当n等于0时,dp[0]为0;并且每次每次先初始化dp[i] = i,即表示为i时的最大所需完全平方根的个数为i个1
3.状态转移:假设当前的数为i,则第一步先从i往前找到一个在数值上最接近i的完全平方数K,K的完全平方根为j(即K = j * j)则此时数值上还剩余i - j * j,则第二步就是去在动态转移方程中查找i - j*j所需的最小完全平方根的个数再加上刚刚找到的一个数K;综上动态转移方程为:dp[i] = min(dp[i], dp[i - j * j]) + 1

复杂度

时间复杂度:

O ( n ⋅ n ) O(n \cdot \sqrt{n}) O(nn );其中 n n n为给定的数;

空间复杂度:

O ( n ) O(n) O(n)

Code

class Solution {/*** Return the least number of perfect square numbers that sum to n.** @param n Given number* @return int*/public int numSquares(int n) {int[] dp = new int[n + 1];for (int i = 1; i <= n; ++i) {dp[i] = i;for (int j = 1; i - j * j >= 0; ++j) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

相关文章:

  • 赶紧收藏!2024 年最常见 20道 Redis面试题(四)
  • 《Python编程从入门到实践》day37
  • 小林coding笔记
  • 英语学习笔记24——Give me/us/him/her/them some ...
  • 5.23小结
  • 【vue-3】动态属性绑定v-bind
  • JPHS-JMIR Public Health and Surveillance
  • Java设计模式-中介者模式(20)
  • SpringBoot前置知识02-spring注解发展史
  • 【js刷题:数据结构链表之环形链表】
  • LitCTF
  • Unity Render入门
  • cuda 内核启动
  • 前端基础入门三大核心之HTML篇:探索WebAssembly —— 开启网页高性能应用新时代
  • 成都爱尔胡建斌院长提醒近视超过600度,记得每年检查眼底!
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • 4. 路由到控制器 - Laravel从零开始教程
  • Debian下无root权限使用Python访问Oracle
  • JS变量作用域
  • Kibana配置logstash,报表一体化
  • Linux下的乱码问题
  • Python语法速览与机器学习开发环境搭建
  • scrapy学习之路4(itemloder的使用)
  • Spring Cloud Alibaba迁移指南(一):一行代码从 Hystrix 迁移到 Sentinel
  • SQLServer之创建显式事务
  • vuex 学习笔记 01
  • 基于HAProxy的高性能缓存服务器nuster
  • 开发基于以太坊智能合约的DApp
  • 模型微调
  • 漂亮刷新控件-iOS
  • 在Mac OS X上安装 Ruby运行环境
  • HanLP分词命名实体提取详解
  • #NOIP 2014# day.1 T2 联合权值
  • #NOIP 2014#day.2 T1 无限网络发射器选址
  • #使用清华镜像源 安装/更新 指定版本tensorflow
  • (003)SlickEdit Unity的补全
  • (11)工业界推荐系统-小红书推荐场景及内部实践【粗排三塔模型】
  • (2022版)一套教程搞定k8s安装到实战 | RBAC
  • (2024,LoRA,全量微调,低秩,强正则化,缓解遗忘,多样性)LoRA 学习更少,遗忘更少
  • (C11) 泛型表达式
  • (NO.00004)iOS实现打砖块游戏(十二):伸缩自如,我是如意金箍棒(上)!
  • (附源码)python旅游推荐系统 毕业设计 250623
  • (附源码)springboot车辆管理系统 毕业设计 031034
  • (附源码)springboot猪场管理系统 毕业设计 160901
  • (三维重建学习)已有位姿放入colmap和3D Gaussian Splatting训练
  • (算法设计与分析)第一章算法概述-习题
  • (转)http协议
  • (转)自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
  • ***linux下安装xampp,XAMPP目录结构(阿里云安装xampp)
  • .NET Core6.0 MVC+layui+SqlSugar 简单增删改查
  • .netcore 如何获取系统中所有session_ASP.NET Core如何解决分布式Session一致性问题
  • .NET教程 - 字符串 编码 正则表达式(String Encoding Regular Express)
  • .net用HTML开发怎么调试,如何使用ASP.NET MVC在调试中查看控制器生成的html?
  • .NET中winform传递参数至Url并获得返回值或文件
  • .net中的Queue和Stack