【Hot100】LeetCode—279. 完全平方数


题目


1- 思路

思路

  • 动规五部曲

2- 实现

⭐完全平方数——题解思路

在这里插入图片描述

class Solution {
    public int numSquares(int n) {
        
        // 1. 定义 dp
        int[] dp = new int[n+1];

        //2. 递推公式
        // dp[j] = Math.min(dp[j],dp[j-i*i]+1);

        //3. 初始化
        int max = Integer.MAX_VALUE;
        for(int i = 0 ; i < dp.length;i++){
            dp[i] = max;
        }
        dp[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);
            }
        }
        return dp[n];
     }
}

3- ACM 实现

public class squareNum {

    public static int numSquares(int n){
        int[] dp = new int[n+1];

        // 2. 递推公式
        // dp[j] = Math.min(j-i*i+1,dp[j]);

        // 3.初始化
        int MAX = Integer.MAX_VALUE;
        for (int i = 0 ; i <= n;i++){
            dp[i] = MAX;
        }
        dp[0] = 0;

        //4. 先遍历 物品 后遍历背包
        for(int i = 1; i*i <= n;i++){
            for(int j = i*i ; j <= n;j++){
                dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入要求的完全平方数和");
        int n = sc.nextInt();

        System.out.println("结果是"+numSquares(n));
    }
}


相关推荐

  1. Leetcode279.完全平方

    2024-07-23 07:20:01       42 阅读
  2. LeetCode279 完全平方

    2024-07-23 07:20:01       40 阅读
  3. leetcode 279.完全平方

    2024-07-23 07:20:01       43 阅读
  4. 279. 完全平方

    2024-07-23 07:20:01       46 阅读
  5. 279. 完全平方

    2024-07-23 07:20:01       45 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 07:20:01       171 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 07:20:01       189 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 07:20:01       157 阅读
  4. Python语言-面向对象

    2024-07-23 07:20:01       170 阅读

热门阅读

  1. 【通俗理解】对数边缘似然:公式与应用

    2024-07-23 07:20:01       32 阅读
  2. mariadb安装centos再次踩坑

    2024-07-23 07:20:01       35 阅读
  3. PostgreSQL 8.4 ROW_NUMBER()函数

    2024-07-23 07:20:01       29 阅读
  4. 通过队列名寻找某队列-linux

    2024-07-23 07:20:01       26 阅读
  5. springboot业务逻辑写在controller层吗

    2024-07-23 07:20:01       29 阅读
  6. linux本地互传文件

    2024-07-23 07:20:01       27 阅读
  7. 异步TCP服务器;异步TCP客户端

    2024-07-23 07:20:01       29 阅读
  8. 【摸鱼笔记】了解itertools,优雅处理list

    2024-07-23 07:20:01       29 阅读
  9. Windows图形界面(GUI)-DLG-C/C++ - 滑动条(Trackbar)

    2024-07-23 07:20:01       33 阅读
  10. 【ffmpeg命令入门】再论ffmpeg通用选项

    2024-07-23 07:20:01       27 阅读
  11. windows启动不打开窗口命令

    2024-07-23 07:20:01       31 阅读
  12. Python应用—浅谈利用opencv去除水印

    2024-07-23 07:20:01       28 阅读