【算法基础:动态规划】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。请按照以下步骤进行操作: 打开浏览器…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
