闫氏DP分析法应用

闫氏DP分析法应用:最大化整数拆分问题


1. 状态表示(化零为整)

1.1 集合的定义

我们首先需要定义一个表示状态的集合。我们将考虑拆分的所有可能性,并且定义集合的属性:

  • 集合:( S(n) ) 表示所有拆分整数 ( n ) 的方案集合。

    • 每个拆分方式由若干个正整数组成,这些正整数之和为 ( n )。
    • 例如,( S(5) ) 的拆分方式有 ( (4, 1), (3, 2), (2, 2, 1), (1, 1, 1, 1, 1) ),每个拆分方式的乘积也需要计算。
  • 属性:我们需要最大化这些拆分方式的乘积。因此,( dp[n] ) 表示整数 ( n ) 的最大拆分乘积。

具体地:

  • 状态表示:对于给定的 ( n ),( dp[n] ) 表示整数 ( n ) 拆分后的最大乘积。

2. 状态计算(化整为零)

在状态表示明确后,我们需要设计状态转移方程,推导出如何从小的子问题推导到大的问题。

2.1 子集划分:

为了计算 ( dp[n] ),我们考虑将 ( n ) 拆分成两个部分 ( j ) 和 ( n-j )。对于每个 ( j )(( 1 \leq j < n )),我们有两种情况:

  • 不选 ( n-j ) 继续拆分:如果选择拆分为 ( j ) 和 ( n-j ),那么直接计算它们的乘积 ( j \times (n-j) )。

  • 选 ( n-j ) 继续拆分:如果 ( n-j ) 继续拆分,使用已求得的最优解 ( dp[n-j] ),并计算乘积 ( j \times dp[n-j] )。

因此,状态转移的关键是选择每个 ( j ) 对应的拆分方式,并计算它们的最大乘积。

2.2 状态转移方程:

根据以上分析,我们可以得到状态转移方程:
d p [ n ] = max ⁡ 1 ≤ j < n { max ⁡ ( j × ( n − j ) , j × d p [ n − j ] ) } dp[n] = \max_{1 \leq j < n} \{ \max(j \times (n-j), j \times dp[n-j]) \} dp[n]=1j<nmax{max(j×(nj),j×dp[nj])}

  • 解释
    • 第一部分 ( j \times (n-j) ) 表示不再拆分 ( n-j ) 的情况,直接计算拆分 ( j ) 和 ( n-j ) 的乘积。
    • 第二部分 ( j \times dp[n-j] ) 表示继续递归拆分 ( n-j ),然后乘上 ( j )。
2.3 初始化条件:

为了开始递推,我们需要初始化一些基础值:

  • ( dp[1] = 1 )(虽然不拆分,但这是递归的基准)。
  • ( dp[2] = 1 )(2 拆分为 1 和 1,乘积为 1)。

3. 示例推导 ( n = 5 )

接下来,我们使用闫氏DP分析法,逐步计算 ( dp[5] ):

3.1 初始化
  • ( dp[1] = 1 )
  • ( dp[2] = 1 )
3.2 递推计算 ( dp[3] )

我们根据状态转移方程计算 ( dp[3] ):

  • 对于 ( j = 1 ):( dp[3] = \max(1 \times 2, 1 \times dp[2]) = \max(2, 1) = 2 )
  • 对于 ( j = 2 ):( dp[3] = \max(2 \times 1, 2 \times dp[1]) = \max(2, 2) = 2 )

因此,( dp[3] = 2 )。

3.3 递推计算 ( dp[4] )

继续递推,计算 ( dp[4] ):

  • 对于 ( j = 1 ):( dp[4] = \max(1 \times 3, 1 \times dp[3]) = \max(3, 2) = 3 )
  • 对于 ( j = 2 ):( dp[4] = \max(2 \times 2, 2 \times dp[2]) = \max(4, 2) = 4 )
  • 对于 ( j = 3 ):( dp[4] = \max(3 \times 1, 3 \times dp[1]) = \max(3, 3) = 3 )

因此,( dp[4] = 4 )。

3.4 递推计算 ( dp[5] )

最终计算 ( dp[5] ):

  • 对于 ( j = 1 ):( dp[5] = \max(1 \times 4, 1 \times dp[4]) = \max(4, 4) = 4 )
  • 对于 ( j = 2 ):( dp[5] = \max(2 \times 3, 2 \times dp[3]) = \max(6, 4) = 6 )
  • 对于 ( j = 3 ):( dp[5] = \max(3 \times 2, 3 \times dp[2]) = \max(6, 3) = 6 )
  • 对于 ( j = 4 ):( dp[5] = \max(4 \times 1, 4 \times dp[1]) = \max(4, 4) = 4 )

因此,( dp[5] = 6 )。

最终答案:( dp[5] = 6 )


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/474518.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

每日OJ题_牛客_天使果冻_递推_C++_Java

目录 牛客_天使果冻_递推 题目解析 C代码 Java代码 牛客_天使果冻_递推 天使果冻 描述&#xff1a; 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻&#xff0c;但她想把最好吃的果冻留到最后收藏。天使想知道前 x个果冻中&#xff0c;美味…

C++AVL平衡树

1.AVL平衡树节点定义 每一个节点都配左右孩子和父节点&#xff0c;以及平衡因子和其所对应的值。 template<class K, class V> struct AVLTreeNode {// 需要parent指针&#xff0c;后续更新平衡因子可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTr…

Vue3 pinia使用

Pinia 是一个现代的状态管理库&#xff0c;专为 Vue 3 设计。它提供了一种简单、直观的方式来管理应用中的全局状态 (就是不同组件都希望去共享的一些变量,函数等)。Pinia 的设计灵感来自于 Vuex&#xff08;Vue 2 的状态管理库&#xff09;&#xff0c;但进行了许多改进&#…

PHP开发全新UI多语言多商户跨境商城源码、支持一键铺货、一键下单

商家可在平台产品库选品&#xff0c;一键铺货到自己商店&#xff0c;用户下单后&#xff0c;商家提交订单给平台&#xff0c;扣除商家供货价所需余额&#xff0c;提交后由平台发货&#xff0c;收货后订单金额结算给商家. 源码开源完整&#xff0c;一切能跑通的逻辑流程都可以二…

移动应用开发:使用Android Studio 实现登录页与注册页跳转

文章目录 前期一&#xff0c;添加UI控件触发跳转二&#xff0c;编写LoginActivity活动代码三&#xff0c;运行程序查看效果 前期 需创建两个活动页面&#xff0c;登录页和注册页&#xff0c;可参考&#xff1a;《Android Studio实现简易登录页》《Android Studio实现简易注册页…

【东莞石碣】戴尔R740服务器维修raid硬盘问题

1&#xff1a;石碣某塑料工厂下午报修一台戴尔R740服务器硬盘故障&#xff0c;催的还比较着急。 2&#xff1a;工程师经过跟用户确认故障的问题以及故障服务器型号和故障硬盘型号&#xff0c;产品和配件确认好后&#xff0c;公司仓库确认有该款硬盘现货&#xff0c;DELL 12T S…

Inpaint-Web:纯浏览器端实现的开源图像处理工具

之前在刷短视频的时候&#xff0c;经常看到一些情侣在景区拍照&#xff0c;结果被路人“抢镜”。有时男朋友会拿出手机&#xff0c;帮忙把那些路人“P”掉&#xff0c;简直是既贴心又有趣。最近我在逛 GitHub 时&#xff0c;发现了一个可以在浏览器端删除照片中部分内容的纯前端…

IDEA2023 SpringBoot整合Web开发(二)

一、SpringBoot介绍 由Pivotal团队提供的全新框架&#xff0c;其设计目的是用来简化Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。SpringBoot提供了一种新的编程范式&#xff0c;可以更加快速便捷…

技术速递|Microsoft.Extensions.VectorData 预览版简介

作者&#xff1a;Luis Quintanilla - 项目经理 排版&#xff1a;Alan Wang 我们很高兴推出 Microsoft.Extensions.VectorData.Abstractions 库&#xff0c;该库现已提供预览版。 正如 Microsoft.Extensions.AI 库为使用 AI 服务提供了一个统一层一样&#xff0c;此包为 .NET 生…

React解决保存less文件后会自动生成css文件的方法

背景&#xff1a;在项目中使用了less&#xff0c;用的是vscode中esay less插件&#xff0c;但在每次保存.less文件时&#xff0c;都会在对应的同级文件夹内生成一个.css文件&#xff0c;如何避免这样的情况呢&#xff1f; 解决办法&#xff1a;在同级目录下的.vscode文件夹&…

初级数据结构——栈与队列的互相实现

目录 前言一、用栈实现队列操作&#xff1a;c代码模版经典例题 二、用队列实现栈操作&#xff1a;c代码模版经典例题 三、总结四、结语 前言 通过我之前的作品已经初步理解了栈和队列的数据结构&#xff0c;这期我们来学习如何实现这两个数据结构的互相转换。在计算机科学中&a…

Qt的一个基本用户登录界面编写|| 从0搭建QT的信号与槽的应用案例 ||Qt样式表的应用

目录 1.新建1个qt项目&#xff0c;基类选中QWidget 2.ui文件布局 3.头文件 3.1 explicit的作用 具体解释 示例 4.cpp源文件 5.信号与槽的应用 6.qt实现效果 7.qt样式表的应用 1.新建1个qt项目&#xff0c;基类选中QWidget 2.ui文件布局 3.头文件 #ifndef WIDADMINLO…

【Apache Paimon】-- 2 -- 核心特性 (0.9.0)

目录 1、实时更新 1.1、实时大批量更新 1.2、支持定义合并引擎 1.3、支持定义更新日志生成器 2、海量数据追加处理 2.1、append table 2.2、快速查询 3、数据湖功能&#xff08;类比&#xff1a;hudi、iceberg、delta&#xff09; 3.1、支持 ACID 事务 3.2、支持 Time…

webpack配置

4-3vue-loader测试_哔哩哔哩_bilibili 一.新建文件夹vue_todo&#xff0c;vscode打开 二.ctrl打开终端&#xff0c;输入npm init -y&#xff0c;快速生成一个默认的package.json文件 之后左边出现项目初始化文件package.json 三.接下来需要webpack完成打包&#xff0c;所以安装…

5.STM32之通信接口《精讲》之USART通信---实验串口接收程序

根据上节&#xff0c;我们一已经完成了串口发送程序的代码&#xff0c;并且深入的解析探索了串口的原理&#xff0c;接下来&#xff0c;Whappy小编将带领大家进入串口接收程序的探索与实验&#xff0c;并将结合上一节串口发送一起来完成串口的发送和接收实验。 上来两张图 上图…

leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重叠

题目 矩形以列表 [x1, y1, x2, y2] 的形式表示&#xff0c;其中 (x1, y1) 为左下角的坐标&#xff0c;(x2, y2) 是右上角的坐标。 矩形的上下边平行于 x 轴&#xff0c;左右边平行于 y 轴。 如果相交的面积为 正 &#xff0c;则称两矩形重叠。 需要明确的是&#xff0c;只在…

ASP.NET MVC宠物商城系统

该系统采用B/S架构&#xff0c;使用C#编程语言进行开发&#xff0c;以ASP.NET MVC框架为基础&#xff0c;以Visual Studio 2019为开发工具&#xff0c;数据库采用SQL Server进行保存数据。系统主要功能包括登录注册、宠物展示、个人中心、我的订单、购物车、用户管理、宠物类别…

最优化方法_罚函数法例题

1 外点罚函数 算法1 外点罚函数法 给定初点&#xff0c;初始罚因子,放大系数&#xff0c;允许误差&#xff0c;置k1。以为初始点&#xff0c;求解无约束问题得最优解。如果,则停止计算&#xff0c;为约束问题的近似最优解&#xff1b;否 则&#xff0c;增大罚因子&#xff0c;令…

python调用MySql保姆级教程(包会的)

目录 一、下载MySql 二、安装MySql 三、验证MySql是否OK 1、MySQL控制台验证 2、命令提示符cmd窗口验证 四、Python调用MySql 4.1 安装pysql 4.2 使用pysql 4.2.1、连接数据库服务器并且创建数据库和表 4.2.2 、将人脸识别考勤系统识别到的数据自动填入到数据库的表单中…

【鸿蒙生态崛起,开发者有哪些机遇与挑战?】HarmonyOS NEXT 引领数字化未来

文章目录 前言一、HarmonyOS NEXT 特点与升级二、全面突破操作系统核心技术三、鸿蒙生态全面守护用户隐私四、鸿蒙生态的崛起与开发者机遇五、全新鸿蒙生态引领数字化未来小结 前言 鸿蒙系统不断发展&#xff0c;有与安卓、iOS 形成三足鼎立之势&#xff0c;且其在智能手机、智…