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

豆包MarsCode算法题:最小周长巧克力板组合

问题描述

在这里插入图片描述


思路分析

这道题可以抽象为一个最优化问题:

问题分析

  • 每个正方形的面积为 ,对应的边长为 k ,周长为 4k
  • 给定整数 n ,我们需要找到若干正方形,使得它们的面积之和恰好等于 n
    在这里插入图片描述
    同时尽量最小化这些正方形的周长总和:
    在这里插入图片描述

解题方法

为了找到最优解,我们可以使用动态规划。

1. 动态规划的定义

dp[i] 表示面积为 i 时的最小周长。
最终答案即为 dp[n]

2. 状态转移方程

对于任意 i ,尝试使用边长为 k 的正方形:

  • 面积为 i 时,如果选择一个边长为 k 的正方形,其面积是 ,对应周长为 4k
  • 转移方程为:
    在这里插入图片描述
    其中 k 是满足 k² ≤ i 的所有正方形边长。

3. 初始条件

  • dp[0]=0:面积为 0 时,总周长为 0
  • 对于 i > 0,初始值设置为无穷大(表示尚未计算)。

4. 求解顺序

从小到大遍历面积 i ,对每个 i 再遍历所有可能的 k ,逐步计算出最优解。


参考代码(Java)

import java.util.Arrays;public class Main {public static int solution(int n) {// 动态规划数组,存储面积为 i 时的最小周长int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值dp[0] = 0; // 面积为 0 时周长为 0// 遍历每个面积for (int i = 1; i <= n; i++) {// 遍历所有可能的正方形边长 kfor (int k = 1; k * k <= i; k++) {dp[i] = Math.min(dp[i], dp[i - k * k] + 4 * k);}}return dp[n];}public static void main(String[] args) {System.out.println(solution(11) == 20); System.out.println(solution(13) == 20); System.out.println(solution(25) == 20); }
}

代码分析

1. 初始化部分

int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值
dp[0] = 0; // 面积为 0 时周长为 0
  • dp[i] 的含义
    dp[i] 表示当总面积为 ( i ) 时,最小的周长和。

  • 初始化逻辑

    • 将所有 dp[i] 初始化为一个大值(Integer.MAX_VALUE),表示尚未计算过或者无效状态。
    • 特殊情况:dp[0] = 0,表示面积为 0 时,周长为 0(无需使用任何正方形)。

2. 外层循环:遍历面积

for (int i = 1; i <= n; i++) {
  • 目的
    从面积 1n ,依次计算每个面积的最小周长。

3. 内层循环:尝试不同正方形

for (int k = 1; k * k <= i; k++) {dp[i] = Math.min(dp[i], dp[i - k * k] + 4 * k);
}
  • 逻辑

    • k 是正方形的边长。
    • 是正方形的面积。
    • 4k 是正方形的周长。
  • 核心转移
    对于当前面积 i ,尝试所有可能的正方形面积 ,更新最优解:
    在这里插入图片描述

    • dp[i - k²] 表示面积减去 后的最优周长。
    • + 4k 是新增正方形的周长。
  • 条件 k * k <= i
    仅考虑 ( k ) 的平方不超过当前面积 ( i ),否则超出范围。

4. 返回结果

return dp[n];
  • 最终,返回 dp[n],即面积为 n 的最小周长和。

复杂度分析

时间复杂度

  • 总时间复杂度为:O(n√n)

空间复杂度

  • 仅使用一个大小为 n+1 的数组 dp,空间复杂度为 O(n)

相关文章:

豆包MarsCode算法题:最小周长巧克力板组合

问题描述 思路分析 这道题可以抽象为一个最优化问题&#xff1a; 问题分析 每个正方形的面积为 k &#xff0c;对应的边长为 k &#xff0c;周长为 4k 。给定整数 n &#xff0c;我们需要找到若干正方形&#xff0c;使得它们的面积之和恰好等于 n&#xff1a; 同时尽量最小…...

vue项目添加骨架屏vue-skeleton-webpack-plugin,通过app.vue添加骨架屏,解决衔接空白问题

安装插件 yarn add vue-skeleton-webpack-plugin在 webpack 中引入插件&#xff1a;以4版本为例配置如下 vue.config.js plugins: [new SkeletonWebpackPlugin({webpackConfig: {entry: {app: path.join(__dirname, ./src/components/entry-skeleton.js),},},minimize: true,…...

测试实项中的偶必现难测bug之模糊匹配逻辑

问题: 现在有一个场景,如果只是通过功能测试会比较难测,例如刚开始我们做会员的时候,只有白银会员,在用户分群的场景下,需要用条件逻辑匹配,当时开发用了like的匹配方式没有问题。1年后加了白银试用会员,导致在统计会员分群的时候明明条件选的是白银会员,但是统计的数…...

Vue:后端返回二进制文件,前端如何实现浏览器自动下载?

Vue项目开发中&#xff0c;遇到界面下载功能时&#xff0c;前端如何实现将后端返回二进制文件在浏览器自动下载&#xff1f; 一、关键代码&#xff1a; export function downloadFile(fileName) {axios({method: post,url: process.env.VUE_APP_BASE_API /cgi-bin/file,data:…...

Android解压zip文件到指定目录

很多时候需要把一个预制的zip文件解压到根目录&#xff0c;下面是一个实例代码&#xff1a; private static final int BUFFER_SIZE 4096;public static void unZip(String zipFilePath, String targetDir) throws IOException {File destDir new File(targetDir);if (!destD…...

主要用于图像的颜色提取、替换以及区域修改

这段代码涉及了以下几个关键步骤&#xff0c;主要用于图像的颜色提取、替换以及区域修改。下面是对代码的详细解析&#xff1a; 1. 导入库 import cv2 import matplotlib.pyplot as plt import numpy as npcv2: OpenCV库&#xff0c;用于图像处理。matplotlib.pyplot: 用于绘…...

gbase8c之运维操作

导出结构&#xff1a; gs_dump -U gbase8s -W Password123 -f /tmp/dump_only_structure.sql -p 15400 sids_station -n public -s -F p 导出数据&#xff1a; gs_dump -U gbase8s -W Password123 -f /tmp/dump_only_data.sql -p 15400 sids_station -n public -a -F p 导入…...

云原生学习

1、云原生学习 文章目录 1、云原生学习1. 介绍2. Docker容器化 1. 介绍 什么是云原生&#xff1f;原生指使用JAVA等语言编写的项目&#xff0c;云是指将项目部署到云服务器上云平台&#xff1a;公有云、私有云 本地平台是指直接部署在自己计算机&#xff0c;而开发的应用一定要…...

深入解析 Vue 3 中的 defineExpose

深入解析 Vue 3 中的 defineExpose 在 Vue 3 的组合式 API&#xff08;Composition API&#xff09;中&#xff0c;defineExpose 是一个重要的辅助函数&#xff0c;专门用于在 <script setup> 模式下暴露组件内部的属性和方法给父组件使用。本文将详细解析 defineExpose…...

Docker3:docker基础1

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…...

【UGUI】背包的交互01(道具信息跟随鼠标+道具信息面板显示)

详细程序逻辑过程 初始化物品栏&#xff1a; 在 Awake 方法中&#xff0c;通过标签找到提示框和信息面板。 循环生成10个背包格子&#xff0c;并为每个格子设置图标和名称。 为每个格子添加 UInterMaager232 脚本&#xff0c;以便处理交互事件。 关闭提示框和信息面板&#…...

ubuntu20.04中编译安装gcc 9.2.0

ubuntu20.04中编译安装gcc 9.2.0,步骤如下&#xff1a; #install compile dependence libraries 1&#xff1a;$ sudo apt install libgmp-dev libisl-dev libmpc-dev libmpfr-dev # install gcc 9.2.0 # download source code 2&#xff1a;$ wget http://ftp.gnu.org/gn…...

ss 命令的基本用法

ss 命令的基本用法 ss [选项]-tanl 选项解释 -t&#xff1a;显示 TCP 连接。-a&#xff1a;显示所有连接&#xff08;包括监听端口&#xff09;。-n&#xff1a;显示数字形式的地址和端口号&#xff0c;而不是解析为主机名和服务名。-l&#xff1a;仅显示监听的端口。 使用示…...

Leetcode198. 打家劫舍(HOT100)

代码&#xff1a; class Solution { public:int rob(vector<int>& nums) {int n nums.size();vector<int> f(n 1), g(n 1);for (int i 1; i < n; i) {f[i] g[i - 1] nums[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[n], g[n]);} }; 这种求…...

kafka基础

文章目录 一、Kafka入门1.1、JMS1.2、生产者-消费者模式1.3、ZooKeeper 二、kafka基础架构2.1、producer2.2、kafka cluster2.2.1、broker2.2.2、Controller2.2.3、Topic2.2.4、Partition2.2.5、Replication2.2.6、Leader & Follower 2.3、consumer 一、Kafka入门 Kafka是一…...

STM32CUBEIDE FreeRTOS操作教程(九):eventgroup事件标志组

STM32CUBEIDE FreeRTOS操作教程&#xff08;九&#xff09;&#xff1a;eventgroup事件标志组 STM32CUBE开发环境集成了STM32 HAL库进行FreeRTOS配置和开发的组件&#xff0c;不需要用户自己进行FreeRTOS的移植。这里介绍最简化的用户操作类应用教程。以STM32F401RCT6开发板为…...

Python设计模式详解之2 —— 工厂模式

工厂模式&#xff08;Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;旨在定义一个用于创建对象的接口&#xff0c;但由子类决定实例化哪个类。工厂模式可以帮助我们将对象的创建与其使用分离&#xff0c;增强代码的可扩展性和维护性。 工厂模式的分类 简单工厂…...

【Zookeeper】二、主从应用(master-worker架构)

以一张具有代表性的架构风格展开本篇论述 一般在这种架构中&#xff0c;主节点所负责的工作主要有 跟踪从节点状态分配任务到从节点&#xff0c;并跟踪任务的有效性&#xff08;任务是否正常执行完成&#xff09; 此时&#xff0c;我们需要关注三个问题 主节点崩溃 如果主节…...

Diffusion【2】:VAE

系列文章目录 文章目录 系列文章目录前言1. Abstract2. Introduction2.1. Motivation2.2. Contribution 3. Methods3.1. Problem Scenario3.2. The variational bound3.3. The SGVB estimator and AEVB algorithm3.3.1. Stochastic Gradient Variational Bayes Estimator3.3.2.…...

高级java每日一道面试题-2024年11月19日-基本篇-获取一个类Class对象的方式有哪些?

如果有遗漏,评论区告诉我进行补充 面试官: 获取一个类Class对象的方式有哪些? 我回答: 在 Java 中&#xff0c;获取一个类的 Class 对象有多种方式。这些方式各有优缺点&#xff0c;适用于不同的场景。以下是常见的几种方法及其详细解释&#xff1a; 1. 使用 new 关键字实…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

Excel 怎么让透视表以正常Excel表格形式显示

目录 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总 1、创建数据透视表 2、设计 》报表布局 》以表格形式显示 3、设计 》分类汇总 》不显示分类汇总...

电脑定时关机工具推荐

软件介绍 本文介绍一款轻量级的电脑自动关机工具&#xff0c;无需安装&#xff0c;使用简单&#xff0c;可满足定时关机需求。 工具简介 这款关机助手是一款无需安装的小型软件&#xff0c;文件体积仅60KB&#xff0c;下载后可直接运行&#xff0c;无需复杂配置。 使用…...

Xcode 16.2 版本 pod init 报错

Xcode 版本升级到 16.2 后&#xff0c;项目执行 pod init 报错&#xff1b; ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchron…...