当前位置: 首页 > 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; 打开浏览器…...

Qt6 + OpenGL 3.3 渲染环境搭建全指南:从空白窗口到专属渲染画布的优雅实现

✨ Qt6 OpenGL 3.3 渲染环境搭建全指南&#xff1a;从空白窗口到专属渲染画布的优雅实现&#x1f4cc; 前置环境准备&#x1f527; 第一步&#xff1a;创建Qt Widget Application 工程&#x1f3a8; 第二步&#xff1a;界面元素搭建与QSS样式美化2.1 核心界面元素搭建2.2 QSS样…...

Node.js——util工具模块

util工具模块1、util模块概述2、util模块的使用2.1、格式化输出字符串2.2、将对象转换为字符串&#xff08;调试&#xff09;2.3、实现对象间的原型继承2.4、转换异步函数的风格2.5、判断是否为指定类型的内置对象2.6、其它方法1、util模块概述 util模块是Node.js的内置模块&a…...

SeqGPT-560M智能客服问答系统部署指南

SeqGPT-560M智能客服问答系统部署指南 1. 引言 想象一下这样的场景&#xff1a;你的电商平台每天收到上千条客户咨询&#xff0c;从"这个衣服有货吗"到"怎么申请退货"&#xff0c;问题五花八门。传统客服需要一个个手动回复&#xff0c;效率低下还容易出…...

Qwen-Image镜像实战:基于RTX4090D,轻松实现图片问答与内容分析

Qwen-Image镜像实战&#xff1a;基于RTX4090D&#xff0c;轻松实现图片问答与内容分析 1. 引言&#xff1a;Qwen-Image镜像的核心价值 在当今多模态AI技术快速发展的背景下&#xff0c;能够同时理解图像和文本的视觉语言模型正变得越来越重要。Qwen-Image作为通义千问系列中的…...

打字侠全面支持三大五笔输入法:初学者快速上手指南

1. 五笔输入法&#xff1a;为什么值得初学者投入时间&#xff1f; 在拼音输入法大行其道的今天&#xff0c;很多初学者可能会疑惑&#xff1a;为什么要花时间学习看起来更复杂的五笔输入法&#xff1f;其实答案很简单——效率。我十年前刚开始接触五笔时也有同样的困惑&#xf…...

【大英赛】2009-2026年大英赛ABCD类历年真题、样卷、听力音频及答案PDF电子版

2026年大英赛将于4月12日9:00—11:00举行&#xff0c;开始倒计时啦&#xff01;小编整理了最新的2009-2026年大学生英语竞赛&#xff08;大英赛NECCS&#xff09;ABCD类历年真题、样卷、听力音频及答案解析&#xff0c;PDF电子版&#xff0c;可下载打印&#xff01; 资料下载&a…...

从idea ai插件到在线原型:用快马平台快速构建你的智能代码生成器

最近在开发中频繁使用IDEA的AI插件辅助编码&#xff0c;发现这类工具能大幅减少重复劳动。但插件功能往往局限于当前IDE环境&#xff0c;于是萌生了一个想法&#xff1a;能否把这种智能生成能力搬到线上&#xff0c;做成一个轻量级的Web工具&#xff1f;经过在InsCode(快马)平台…...

Janus-Pro-7B效果展示:手写体/表格/多语言混合OCR识别准确率实测

Janus-Pro-7B效果展示&#xff1a;手写体/表格/多语言混合OCR识别准确率实测 1. 引言 你有没有遇到过这样的场景&#xff1f;翻出一张老照片&#xff0c;背面是长辈用钢笔写下的寄语&#xff0c;字迹有些潦草&#xff0c;想把它转成电子版保存&#xff0c;却一个字也认不出来…...

Visio高效绘制神经网络卷积层:从基础到三维呈现

1. Visio绘制神经网络卷积层的入门指南 第一次用Visio画神经网络结构时&#xff0c;我盯着满屏的工具栏发懵——这玩意儿比Photoshop的图层还复杂。但摸索半天后发现&#xff0c;只要掌握几个核心功能&#xff0c;画卷积层其实比用PPT简单十倍。先说说最基础的形状选择&#xf…...

73:L的程序安全:蓝队的规范防御

作者&#xff1a; HOS(安全风信子) 日期&#xff1a; 2026-03-26 主要来源平台&#xff1a; GitHub 摘要&#xff1a; 程序安全是防御的基石&#xff0c;通过规范的流程、自动化执行和可追溯设计构建可靠的安全防御体系。本文分享程序安全的核心价值、L的程序安全策略、技术实现…...