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

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...