当前位置: 首页 > news >正文

【算法基础:动态规划】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(整数拆分、分拆数)

文章目录 例题&#xff1a;900. 整数划分解法1——完全背包解法2——分拆数⭐⭐⭐ 例题&#xff1a;900. 整数划分 https://www.acwing.com/problem/content/902/ 解法1——完全背包 容量是 n&#xff0c;物品的大小和价值是 1 ~ n 中的所有数字。 import java.util.*;pub…...

封装(Encapsulation)

目录 概念 好处 数据隐藏 模块化设计 代码复用 简化接口 示例 意义 概念 封装&#xff08;Encapsulation&#xff09;是面向对象编程的一个核心概念&#xff0c;它指的是将数据和相关操作封装在一个对象中&#xff0c;隐藏了实现的细节。&#xff08;就是实现数据封装和…...

php 原型模式

一&#xff0c;原型模式&#xff0c;就是先创建好一个原型对象&#xff0c;然后通过拷贝原型对象来生成新的对象。适用于大对象的创建&#xff0c;因为每次new一个大对象会有很大的开销&#xff0c;原型模式仅需内存拷贝即可。 原型模式中的主要角色&#xff1a; 1&#xff0c;…...

LiveGBS流媒体平台GB/T28181功能-支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放

LiveGBS支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放 1、背景2、分屏展示3、选择轮播通道4、配置轮播间隔(秒)5、点击开始轮播6、轮播停止及全屏7、搭建GB28181视频直播平台 1、背景 视频监控项目使用过程中&#xff0c;有时需要大屏值守&#xff0c;值守的时候多分…...

6、Nginx实现反向代理

Nginx 反向代理是一种常见的应用场景&#xff0c;它允许 Nginx 作为中间服务器接收客户端的请求&#xff0c;并代理转发这些请求到后端的真实服务器。这种配置使得客户端只需要与 Nginx 交互&#xff0c;而后端服务器对客户端是透明的。 ngx_http_proxy_module&#xff1a; 将客…...

Leetcode——404 左叶子之和

404. 左叶子之和 难度简单&#xff08;虽然简单 但是我用递归做时 还是有点坑的&#xff09; 给定二叉树的根节点 root &#xff0c;返回所有左叶子之和。 示例 1&#xff1a; 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中&#xff0c;有两个左叶子…...

R并行计算-parallel例子1

前言&#xff1a; 通常&#xff0c;如果进程运行时间超过3分钟&#xff0c;则会考虑使用并行处理。 这听起来可能很复杂&#xff0c;但是并行计算很简单。 当你有一个重复的任务&#xff0c;它占用了你太多宝贵的时间&#xff0c;为什么不使用并行计算来节省时间呢&#xff…...

JavaSE复盘2

Collection接口的接口对象集合&#xff08;单列集合&#xff09; List接口&#xff1a;元素按照先后有序保存&#xff0c;可重复 LinkList接口实现类&#xff0c;链表&#xff0c;随机访问&#xff0c;没有同步&#xff0c;线程不安全ArrayList接口实现类&#xff0c;数组&…...

如何在3ds max中创建可用于真人场景的巨型机器人:第 3 部分

推荐&#xff1a; NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 1. 创建腿部装备 步骤 1 打开 3ds Max。 打开在本教程最后一部分中保存的文件。 打开 3ds Max 步骤 2 转到创建> 系统并单击骨骼。 创建>系统 步骤 3 为的 侧视口中的腿&#xff0c;如下图所示…...

Android性能优化之游戏引擎初始化ANR

近期&#xff0c;着手对bugly上的anr 处理&#xff0c;记录下优化的方向。 借用网上的一张图&#xff1a; 这里的anr 问题是属于主线程的call 耗时操作。需要使用trace 来获取发生anr前一些列的耗时方法调用时间&#xff0c;再次梳理业务&#xff0c;才可能解决。 问题1 ja…...

Jmap-JVM(十六)

上篇文章说了ZGC是jdk11加入的&#xff0c;他是未来jvm垃圾收集器的奠定者&#xff0c;满足TB级别内存处理&#xff0c;STW时间保持在10ms以下。 Jmap 我们可以先通过jmap -histo 进程ip 来查看&#xff0c;但是这样看不太清晰&#xff0c;我们可以用这行命令生成一个文件&…...

【分布式能源的选址与定容】基于多目标粒子群算法分布式电源选址定容规划研究(Matlab代码实现)

目录 &#x1f4a5;1 概述 1.1 功率损耗 ​编辑1.2 电压质量 1.3 DG总容量 &#x1f4da;2 运行结果 &#x1f308;3 Matlab代码实现 &#x1f389;4 参考文献 &#x1f4a5;1 概述 参考文献&#xff1a; 本文采用的是换一个算法解决&#xff0c; 基于基于多目标粒子群算法分布…...

flink源码分析-获取JVM最大堆内存

flink版本: flink-1.11.2 代码位置: org.apache.flink.runtime.util.EnvironmentInformation#getMaxJvmHeapMemory 如果设置了-Xmx参数&#xff0c;就返回这个参数&#xff0c;如果没设置就返回机器物理内存的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是什么&#xff1f; 二、Selenium History 三、Selenium原理 四、Selenium工作过程总结&#xff1a; 五、remote server端的这些功能是如何实现的呢&#xff1f; 六、附&#xff1a; 一、Selenium是什么&#xff1f; 用官网的一句话来讲&#xff1a;Sel…...

java接口实现

文章目录 java接口实现接口中成员组成默认方法静态方法私有接口&#xff08;保证自己的JDK版本大于等于9版本&#xff09;类和接口的关系抽象类与接口之间的区别 java接口实现 1.接口关键字 interface2.接口不能实例化3.类与接口之间的关系是实现关系&#xff0c;通过 impleme…...

数据结构入门指南:链表(新手避坑指南)

目录 前言 1.链表 1.1链表的概念 1.2链表的分类 1.2.1单向或双向 1.2.2.带头或者不带头 1.2.33. 循环或者非循环 1.3链表的实现 定义链表 总结 前言 前边我们学习了顺序表&#xff0c;顺序表是数据结构中最简单的一种线性数据结构&#xff0c;今天我们来学习链表&#x…...

SpringBoot第24讲:SpringBoot集成MySQL - MyBatis XML方式

SpringBoot第24讲&#xff1a;SpringBoot集成MySQL - MyBatis XML方式 上文介绍了用JPA方式的集成MySQL数据库&#xff0c;JPA方式在中国以外地区开发而言基本是标配&#xff0c;在国内MyBatis及其延伸框架较为主流。本文是SpringBoot第24讲&#xff0c;主要介绍MyBatis技栈的演…...

linux 查看网卡,网络情况

1&#xff0c;使用nload命令查看 #yum -y install nload 2&#xff0c; 查看eth0网卡网络情况 #nload eth0 Incoming也就是进入网卡的流量&#xff0c;Outgoing&#xff0c;也就是从这块网卡出去的流量&#xff0c;每一部分都有下面几个。 – Curr&#xff1a;当前流量 – Avg…...

在Mac上搭建Gradle环境

在Mac上搭建Gradle环境&#xff1a; 步骤1&#xff1a;下载并安装Java开发工具包&#xff08;JDK&#xff09; Gradle运行需要Java开发工具包&#xff08;JDK&#xff09;。您可以从Oracle官网下载适合您的操作系统版本的JDK。请按照以下步骤进行操作&#xff1a; 打开浏览器…...

文脉定序详细步骤:自定义prompt模板提升BGE-m3在垂直领域表现

文脉定序详细步骤&#xff1a;自定义prompt模板提升BGE-m3在垂直领域表现 1. 理解文脉定序与BGE-m3的核心价值 文脉定序是一款基于BGE-m3模型的智能语义重排序系统&#xff0c;专门解决传统搜索引擎"搜得到但排不准"的痛点。它通过全交叉注意机制&#xff0c;对问题…...

无需配置环境!MinerU镜像一键部署,即刻体验智能文档解析

无需配置环境&#xff01;MinerU镜像一键部署&#xff0c;即刻体验智能文档解析 1. 为什么选择智能文档解析&#xff1f; 在日常办公和学习中&#xff0c;我们经常需要处理各种文档资料&#xff1a;PDF报告、扫描合同、学术论文、财务报表等。传统方式要么需要手动输入&#…...

数据库优化:高效查询GUID的技巧

在日常的数据库操作中,如何高效地查询数据是一个永恒的话题。特别是当我们处理大型数据集和需要在文本字段中查找特定模式(如GUID)时,查询效率显得尤为关键。今天,我将分享一种优化查询GUID的方法,帮助你从长达数小时的查询时间中解脱出来。 背景 假设我们有一个数据库…...

GEE快速入门:哨兵2号影像批量下载与去云处理指南

1. 为什么选择GEE处理哨兵2号影像&#xff1f; 如果你正在寻找一个免费、高效且无需本地高性能计算机的遥感数据处理方案&#xff0c;Google Earth Engine&#xff08;GEE&#xff09;绝对是你的首选。作为一个云端地理空间分析平台&#xff0c;GEE存储了海量的卫星影像数据&am…...

Phi-3-mini-4k-instruct-gguf多场景落地:客服话术优化、会议纪要提炼、周报生成实战

Phi-3-mini-4k-instruct-gguf多场景落地&#xff1a;客服话术优化、会议纪要提炼、周报生成实战 1. 轻量级文本生成利器介绍 Phi-3-mini-4k-instruct-gguf是微软推出的轻量级文本生成模型&#xff0c;特别适合处理日常办公场景中的文本任务。这个模型体积小巧但能力出众&…...

船舶水动力学与运动控制技术指南:从理论建模到工程实践

船舶水动力学与运动控制技术指南&#xff1a;从理论建模到工程实践 【免费下载链接】FossenHandbook Handbook of Marine Craft Hydrodynamics and Motion Control is an extensive study of the latest research in marine craft hydrodynamics, guidance, navigation, and co…...

新手福音:用快马AI生成带详解注释的Arduino交通灯实验代码

作为一个刚接触单片机的新手&#xff0c;第一次看到Arduino开发板时既兴奋又迷茫。那些闪烁的LED灯和蜂鸣器背后到底藏着什么秘密&#xff1f;今天我就用InsCode(快马)平台来探索一个有趣的交通灯模拟项目&#xff0c;整个过程比想象中简单多了。 项目构思 我想做一个能模拟真实…...

Zabbix 6.0部署避坑指南:为什么你的Ubuntu安装总卡在数据库初始化这一步?

Zabbix 6.0部署避坑指南&#xff1a;为什么你的Ubuntu安装总卡在数据库初始化这一步&#xff1f; 如果你正在Ubuntu上部署Zabbix 6.0&#xff0c;却反复在数据库初始化这一步失败&#xff0c;这篇文章就是为你准备的。不同于常规的安装教程&#xff0c;我们将聚焦于那些看似简…...

OptiScaler完全指南:让你的AMD/Intel显卡也能畅享DLSS级画质增强

OptiScaler完全指南&#xff1a;让你的AMD/Intel显卡也能畅享DLSS级画质增强 【免费下载链接】OptiScaler OptiScaler bridges upscaling/frame gen across GPUs. Supports DLSS2/XeSS/FSR2 inputs, replaces native upscalers, enables FSR3 FG on non-FG titles. Supports Nu…...

Typora与AI结合:使用万象熔炉·丹青幻境为Markdown文档自动配图

Typora与AI结合&#xff1a;使用万象熔炉丹青幻境为Markdown文档自动配图 不知道你有没有过这样的体验&#xff1a;在Typora里写完一篇技术博客或项目文档&#xff0c;内容详实&#xff0c;逻辑清晰&#xff0c;但通篇下来全是文字&#xff0c;总觉得少了点什么。想配几张图吧…...