当前位置: 首页 > 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度,记得每年检查眼底!
  • 分享的文章《人生如棋》
  • [笔记] php常见简单功能及函数
  • [译]Python中的类属性与实例属性的区别
  • 【EOS】Cleos基础
  • co.js - 让异步代码同步化
  • CSS实用技巧
  • DOM的那些事
  • Git的一些常用操作
  • java第三方包学习之lombok
  • Js基础知识(四) - js运行原理与机制
  • Linux编程学习笔记 | Linux多线程学习[2] - 线程的同步
  • Linux中的硬链接与软链接
  • OpenStack安装流程(juno版)- 添加网络服务(neutron)- controller节点
  • PHP那些事儿
  • python_bomb----数据类型总结
  • 利用DataURL技术在网页上显示图片
  • 排序算法学习笔记
  • 判断客户端类型,Android,iOS,PC
  • 前端技术周刊 2018-12-10:前端自动化测试
  • hi-nginx-1.3.4编译安装
  • ​一帧图像的Android之旅 :应用的首个绘制请求
  • #Z2294. 打印树的直径
  • $.ajax()方法详解
  • (3)医疗图像处理:MRI磁共振成像-快速采集--(杨正汉)
  • (Matalb分类预测)GA-BP遗传算法优化BP神经网络的多维分类预测
  • (Redis使用系列) Springboot 整合Redisson 实现分布式锁 七
  • (zt)最盛行的警世狂言(爆笑)
  • (编译到47%失败)to be deleted
  • (附源码)spring boot基于Java的电影院售票与管理系统毕业设计 011449
  • (附源码)springboot 智能停车场系统 毕业设计065415
  • (附源码)ssm学生管理系统 毕业设计 141543
  • (论文阅读26/100)Weakly-supervised learning with convolutional neural networks
  • (转)es进行聚合操作时提示Fielddata is disabled on text fields by default
  • (转)项目管理杂谈-我所期望的新人
  • (轉貼) 蒼井そら挑戰筋肉擂台 (Misc)
  • .[backups@airmail.cc].faust勒索病毒的最新威胁:如何恢复您的数据?
  • .【机器学习】隐马尔可夫模型(Hidden Markov Model,HMM)
  • .NET Core实战项目之CMS 第十二章 开发篇-Dapper封装CURD及仓储代码生成器实现
  • .NET Framework 4.6.2改进了WPF和安全性
  • .Net Framework 4.x 程序到底运行在哪个 CLR 版本之上