当前位置: 首页 > 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 关键字实…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...