【算法基础:动态规划】5.3 计数类DP(整数拆分、分拆数)
文章目录
- 例题:900. 整数划分
- 解法1——完全背包
- 解法2——分拆数⭐⭐⭐
例题:900. 整数划分
https://www.acwing.com/problem/content/902/

解法1——完全背包
容量是 n,物品的大小和价值是 1 ~ n 中的所有数字。
import java.util.*;public class Main {public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();final int MOD = (int)1e9 + 7;int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; ++i) {for (int j = i; j <= n; ++j) {dp[j] = (dp[j] + dp[j - i]) % MOD;}}System.out.println(dp[n]);}
}
解法2——分拆数⭐⭐⭐
状态表示:
f[i][j]表示总和为i,总个数为j的方案数
状态转移方程:
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

从最小值 = 1 的转移过来,就是补上数字1。
从最小值 > 1 的转移过来,就是把每个数字都 + 1。
import java.util.*;public class Main {public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();final int MOD = (int)1e9 + 7;// `f[i][j]`表示总和为i,总个数为j的方案数int[][] dp = new int[n + 1][n + 1];dp[1][1] = 1;for (int i = 2; i <= n; ++i) {for (int j = 1; j <= i; ++j) {dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % MOD;}}int ans = 0;for (int j = 0; j <= n; ++j) {ans = (ans + dp[n][j]) % MOD;}System.out.println(ans);}
}
相关文章:
【算法基础:动态规划】5.3 计数类DP(整数拆分、分拆数)
文章目录 例题:900. 整数划分解法1——完全背包解法2——分拆数⭐⭐⭐ 例题:900. 整数划分 https://www.acwing.com/problem/content/902/ 解法1——完全背包 容量是 n,物品的大小和价值是 1 ~ n 中的所有数字。 import java.util.*;pub…...
封装(Encapsulation)
目录 概念 好处 数据隐藏 模块化设计 代码复用 简化接口 示例 意义 概念 封装(Encapsulation)是面向对象编程的一个核心概念,它指的是将数据和相关操作封装在一个对象中,隐藏了实现的细节。(就是实现数据封装和…...
php 原型模式
一,原型模式,就是先创建好一个原型对象,然后通过拷贝原型对象来生成新的对象。适用于大对象的创建,因为每次new一个大对象会有很大的开销,原型模式仅需内存拷贝即可。 原型模式中的主要角色: 1,…...
LiveGBS流媒体平台GB/T28181功能-支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放
LiveGBS支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放 1、背景2、分屏展示3、选择轮播通道4、配置轮播间隔(秒)5、点击开始轮播6、轮播停止及全屏7、搭建GB28181视频直播平台 1、背景 视频监控项目使用过程中,有时需要大屏值守,值守的时候多分…...
6、Nginx实现反向代理
Nginx 反向代理是一种常见的应用场景,它允许 Nginx 作为中间服务器接收客户端的请求,并代理转发这些请求到后端的真实服务器。这种配置使得客户端只需要与 Nginx 交互,而后端服务器对客户端是透明的。 ngx_http_proxy_module: 将客…...
Leetcode——404 左叶子之和
404. 左叶子之和 难度简单(虽然简单 但是我用递归做时 还是有点坑的) 给定二叉树的根节点 root ,返回所有左叶子之和。 示例 1: 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中,有两个左叶子…...
R并行计算-parallel例子1
前言: 通常,如果进程运行时间超过3分钟,则会考虑使用并行处理。 这听起来可能很复杂,但是并行计算很简单。 当你有一个重复的任务,它占用了你太多宝贵的时间,为什么不使用并行计算来节省时间呢ÿ…...
JavaSE复盘2
Collection接口的接口对象集合(单列集合) List接口:元素按照先后有序保存,可重复 LinkList接口实现类,链表,随机访问,没有同步,线程不安全ArrayList接口实现类,数组&…...
如何在3ds max中创建可用于真人场景的巨型机器人:第 3 部分
推荐: NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 1. 创建腿部装备 步骤 1 打开 3ds Max。 打开在本教程最后一部分中保存的文件。 打开 3ds Max 步骤 2 转到创建> 系统并单击骨骼。 创建>系统 步骤 3 为的 侧视口中的腿,如下图所示…...
Android性能优化之游戏引擎初始化ANR
近期,着手对bugly上的anr 处理,记录下优化的方向。 借用网上的一张图: 这里的anr 问题是属于主线程的call 耗时操作。需要使用trace 来获取发生anr前一些列的耗时方法调用时间,再次梳理业务,才可能解决。 问题1 ja…...
Jmap-JVM(十六)
上篇文章说了ZGC是jdk11加入的,他是未来jvm垃圾收集器的奠定者,满足TB级别内存处理,STW时间保持在10ms以下。 Jmap 我们可以先通过jmap -histo 进程ip 来查看,但是这样看不太清晰,我们可以用这行命令生成一个文件&…...
【分布式能源的选址与定容】基于多目标粒子群算法分布式电源选址定容规划研究(Matlab代码实现)
目录 💥1 概述 1.1 功率损耗 编辑1.2 电压质量 1.3 DG总容量 📚2 运行结果 🌈3 Matlab代码实现 🎉4 参考文献 💥1 概述 参考文献: 本文采用的是换一个算法解决, 基于基于多目标粒子群算法分布…...
flink源码分析-获取JVM最大堆内存
flink版本: flink-1.11.2 代码位置: org.apache.flink.runtime.util.EnvironmentInformation#getMaxJvmHeapMemory 如果设置了-Xmx参数,就返回这个参数,如果没设置就返回机器物理内存的1/4. 这里主要看各个机器内存的获取方法。 /*** The maximum JVM…...
第17节 R语言分析:生物统计数据集 R 编码分析和绘图
生物统计数据集 R 编码分析和绘图 生物统计学,用于对给定文件 data.csv 中的医疗数据应用 R 编码,该文件是患者人口统计数据集,包含有关来自各种祖先谱系的个体的标准信息。 数据集特征解释 脚本 output= file("Output.txt") # File name of output log sink(o…...
一文了解什么是Selenium自动化测试?
目录 一、Selenium是什么? 二、Selenium History 三、Selenium原理 四、Selenium工作过程总结: 五、remote server端的这些功能是如何实现的呢? 六、附: 一、Selenium是什么? 用官网的一句话来讲:Sel…...
java接口实现
文章目录 java接口实现接口中成员组成默认方法静态方法私有接口(保证自己的JDK版本大于等于9版本)类和接口的关系抽象类与接口之间的区别 java接口实现 1.接口关键字 interface2.接口不能实例化3.类与接口之间的关系是实现关系,通过 impleme…...
数据结构入门指南:链表(新手避坑指南)
目录 前言 1.链表 1.1链表的概念 1.2链表的分类 1.2.1单向或双向 1.2.2.带头或者不带头 1.2.33. 循环或者非循环 1.3链表的实现 定义链表 总结 前言 前边我们学习了顺序表,顺序表是数据结构中最简单的一种线性数据结构,今天我们来学习链表&#x…...
SpringBoot第24讲:SpringBoot集成MySQL - MyBatis XML方式
SpringBoot第24讲:SpringBoot集成MySQL - MyBatis XML方式 上文介绍了用JPA方式的集成MySQL数据库,JPA方式在中国以外地区开发而言基本是标配,在国内MyBatis及其延伸框架较为主流。本文是SpringBoot第24讲,主要介绍MyBatis技栈的演…...
linux 查看网卡,网络情况
1,使用nload命令查看 #yum -y install nload 2, 查看eth0网卡网络情况 #nload eth0 Incoming也就是进入网卡的流量,Outgoing,也就是从这块网卡出去的流量,每一部分都有下面几个。 – Curr:当前流量 – Avg…...
在Mac上搭建Gradle环境
在Mac上搭建Gradle环境: 步骤1:下载并安装Java开发工具包(JDK) Gradle运行需要Java开发工具包(JDK)。您可以从Oracle官网下载适合您的操作系统版本的JDK。请按照以下步骤进行操作: 打开浏览器…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
