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

191、【动态规划】AcWing ——AcWing 900. 整数划分:完全背包解法+加减1解法(C++版本)

题目描述

在这里插入图片描述
参考文章:900. 整数划分

解题思路

因为本题中规定了数字从大到小,其实也就是不论是1 + 2 + 1 = 4,还是2 + 1 + 1 = 4,都会被看作是2 + 1 + 1 = 4这一种情况,因此本题是在遍历中不考虑结果顺序。

背包问题中只需考虑使用的物品种类,因此可转化为完全背包问题,将组成的数看作物品且容量为1n,背包容量为n。本题便转化为了,从物品1物品n(体积也是为1~n)中进行选择,构成背包容量为n的方案个数。

(1)完全背包二维数组

  • 动态规划五步曲:

(1)dp[i][j]含义: 从1~i中选择物品,达到背包容量为j的方案个数。

(2)递推公式: dp[i][j]=(dp[i−1][j]+dp[i][j−i])dp[i][j] = (dp[i - 1][j] + dp[i][j - i])dp[i][j]=(dp[i1][j]+dp[i][ji]),完全背包的一般性化简后递推公式,未化简前所表示的是尝试放入物品1到物品j后的情况。

(3)dp数组初始化: dp[i][0] = 1,容量为0时,仅有一种情况。

(4)遍历顺序: 从左到右,从上到下。

(5)举例: (省略)

#include <iostream>using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int dp[N][N];int main() {cin >> n;for(int i = 1; i <= n; i++)         dp[i][0] = 1;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i > j)           dp[i][j] = dp[i - 1][j] % mod;else                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % mod;}}cout << dp[n][n] << endl;return 0;
}

(2)完全背包一维滚动数组

对变量进行优化

#include <iostream>using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int dp[N];int main() {cin >> n;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;}}cout << dp[n] << endl;return 0;
}

(3)用加减1方法

此方法主要使用的是加一个和减一个1,还保持某种方案不变化的特点,得来递推公式。因为我们要求的只是方案个数,

例如:组合成3的方案可以为2、1和1、1、1,当我们想要得到组合成4的方案,那么就可以分别从2、1和1、1、1演化过来,就是2、1、1和1、1、1、1,此时3中这一部分含有最小值为1的方案个数与4中这一部分含有最小值为1的方案个数其实是相同的。

(1)dp[i][j]含义: 由j个数组合成总和为i的方案个数

(2)递推公式: dp[i][j]=dp[i−1][j−1]+dp[i−j][j]dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]dp[i][j]=dp[i1][j1]+dp[ij][j],将状态集合划分成两部分,一部分是j个数中的最小值值是1,另一部分是j个数中的最小值大于1。

对于最小值是1的集合,状态转移为dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i1][j1],意思为当前状态由少一个1的状态演变过来。因为我们要求的是组合成目标数是的方案个数,因此加上一个时,其实还是在此种方案下,故方案个数与dp[i - 1][j - 1]的方案个数相同。

对于最大值大于1的集合,状态转移为dp[i][j]=dp[i−j][j]dp[i][j] = dp[i - j][j]dp[i][j]=dp[ij][j],还是利用1这种特点,将j个数中各自减去一个1,此时dp[i][j]就可以有dp[i - j][j]而来。

(3)dp数组初始化: dp[0][0] = dp[1][1] = 1,重量为0和1时仅有一种方案。

(4)遍历顺序: 从左到右,从上到下。

(5)举例:

例如:组合成3的方案可以为2、1和1、1、1,当我们想要得到组合成4的方案,那么就可以分别从2、1和1、1、1演化过来,就是2、1、1和1、1、1、1,此时3中这一部分含有最小值为1的方案个数与4中这一部分含有最小值为1的方案个数其实是相同的。

#include <iostream>using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int dp[N][N];int main() {cin >> n;dp[0][0] = dp[1][1] = 1;for(int i = 1; i <= n; i++) {for(int j = 1; j <= i; j++) {dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;}}int res = 0;for(int i = 1; i <= n; i++)     res = (dp[n][i] + res) % mod;cout << res << endl;return 0;
}

相关文章:

191、【动态规划】AcWing ——AcWing 900. 整数划分:完全背包解法+加减1解法(C++版本)

题目描述 参考文章&#xff1a;900. 整数划分 解题思路 因为本题中规定了数字从大到小&#xff0c;其实也就是不论是1 2 1 4&#xff0c;还是2 1 1 4&#xff0c;都会被看作是2 1 1 4这一种情况&#xff0c;因此本题是在遍历中不考虑结果顺序。 背包问题中只需考虑…...

Java 比较器

public interface Comparable Comparable 接口位于 java.lang 包下&#xff0c;对实现它的每个类的对象强加一个总排序&#xff0c;这种排序被称为类的自然顺序&#xff0c;compareTo 方法被称为其自然比较方法。 实现此接口的对象的列表&#xff08;和数组&#xff09;可以由…...

配置本地 python GEE、geemap环境

1.安装anconda 百度搜索anconda清华镜像&#xff0c;从清华镜像中选择最新的anconda安装包&#xff0c;国内镜像网站下载速度较快&#xff0c;如果从国外官网下载速度相当慢&#xff0c;详细安装教程请参考&#xff1a; anconda安装教程https://blog.csdn.net/lwbCUMT/article…...

cmd命令教程

小提示&#xff1a; 在本文中&#xff0c;我将向您展示可以在 Windows 命令行上使用的 40 个命令 温馨提示&#xff1a;在本教程中学习使用适用于 Windows 10 和 CMD 网络命令的最常见基本 CMD 命令及其语法和示例 文章目录为什么命令提示符有用一、cmd是什么&#xff1f;如何在…...

深圳大学计软《面向对象的程序设计》实验15 函数模板和类模板

A. 有界数组模板类&#xff08;类模板&#xff09; 题目描述 编写有界数组模板BoundArray&#xff08;即检查对数组元素下标引用并在下标越界时终止程序的执行&#xff09;&#xff0c;能够存储各种类型的数据。要求实现对数组进行排序的方法sort&#xff0c;及对数组进行查找…...

组播详解及示例代码

写在前面 由于公司业务需要用到组播实现&#xff0c;这里就记录下学习过程。在学习组播之前&#xff0c;我们先来看看另外两种数据包传输方式&#xff1a;单播和广播。 单播&#xff1a;简单来说就是数据一对一发送&#xff0c;如果需要给多个主机发送数据时&#xff0c;就需…...

C语言-qsort函数示例解析

一.qsort函数是什么stdlib.h头文件下的函数qsort()函数&#xff1a;是八大排序算法中的快速排序&#xff0c;能够排序任意数据类型的数组其中包括整形&#xff0c;浮点型&#xff0c;字符串甚至还有自定义的结构体类型。qsort函数实现对不同元素的排序主要就是通过对compar函数…...

一些Linux内核内存性能调优笔记!

前言 在工作生活中&#xff0c;我们时常会遇到一些性能问题&#xff1a;比如手机用久了&#xff0c;在滑动窗口或点击 APP 时会出现页面反应慢、卡顿等情况&#xff1b;比如运行在某台服务器上进程的某些性能指标&#xff08;影响用户体验的 PCT99 指标等&#xff09;不达预期…...

【JVM】逃逸分析

开发者都知道&#xff0c;基本上所有对象都是在堆上创建。但是&#xff0c;这里还是没有把话说绝对哈&#xff0c;指的是基本上所有。昨天一位朋友在聊天中&#xff0c;就说了所有对象都在堆中创建&#xff0c;然后被朋友一阵的嘲笑。 开始我们的正文&#xff0c;我们今天来聊聊…...

C51---震动传感器控制LED灯亮灭

1.example #include "reg52.h" sbit led1 P3^7;//原理图中led1指向P3组IO口的P3.7口 sbit vibrate P3^3;//Do接到了P3.3口 void Delay3000ms() //11.0592MHz { unsigned char i, j, k; //_nop_(); i 22; j 3; k 227; do { …...

使用 JaCoCo 生成测试覆盖率报告

0、为什么要生成测试覆盖率报告 在我们实际的工作中&#xff0c;当完成程序的开发后&#xff0c;需要提交给测试人员进行测试&#xff0c;经过测试人员测试后&#xff0c;代码才能上线到生产环境。 有个问题是&#xff1a;怎么能证明程序得到了充分的测试&#xff0c;程序中所…...

windows下neo4j安装及配置,并绘制人物关系图谱

neo4j安装及配置&#xff0c;绘制人物关系图谱 先升级pip&#xff0c;安装py2neo pip install py2neo2021.0.1依赖 jdk1.8&#xff0c; neo4j 3.xx&#xff1b; 或者jdk18&#xff0c;neo4j 4.x&#xff0c;5.x&#xff1b; 官网下载了neo4j4.x,5.x 因为jdk版本原因都不行&am…...

【Spring6】IoC容器之基于XML管理Bean

3、容器&#xff1a;IoC IoC 是 Inversion of Control 的简写&#xff0c;译为“控制反转”&#xff0c;它不是一门技术&#xff0c;而是一种设计思想&#xff0c;是一个重要的面向对象编程法则&#xff0c;能够指导我们如何设计出松耦合、更优良的程序。 Spring 通过 IoC 容…...

Warshall算法求传递闭包及Python编程的实现

弗洛伊德算法-Floyd(Floyd-Warshall)-求多源最短路径&#xff0c;求传递闭包 Floyd算法又称为插点法&#xff0c;是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法&#xff0c; 与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大…...

AcWing第 93 场周赛

4867. 整除数 给定两个整数 n,k&#xff0c;请你找到大于 n 且能被 k 整除的最小整数 x。 输入格式 共一行&#xff0c;包含两个整数 n,k。 输出格式 输出大于 n 且能被 k 整除的最小整数 x。 数据范围 前 4 个测试点满足 1≤n,k≤100。 所有测试点满足 1≤n,k≤109。 …...

计及需求响应的粒子群算法求解风能、光伏、柴油机、储能容量优化配置(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

利用Nginx给RStudio-Server配置https

前篇文档&#xff0c;我这边写了安装RStudio-Server的方法。默认是http的访问方式&#xff0c;现在我们需要将其改成https的访问方式。 1、给服务器安装Nginx&#xff1a;参照之前的安装Nginx的方法。 2、创建/usr/local/nginx/ssl目录&#xff1a; mkdir /usr/local/nginx/ss…...

YOLOv7实验记录

这篇博客主要记录博主在做YOLOv7模型训练与测试过程中遇到的一些问题。 首先我们需要明确YOLO模型权重文件与模型文件的使用 其实在github的readme中已经告诉我们使用方法&#xff0c;但我相信有很多像博主一样眼高手低的人可能会犯类似的错误。 训练 首先是训练时的设置&…...

用Python获取史瓦西时空中克氏符的分量

文章目录三维球面坐标史瓦西时空三维球面坐标 Einsteinpy中提供了克氏符模型&#xff0c;可通过ChristoffelSymbols获取。简单起见&#xff0c;先以最直观的三维球面为例&#xff0c;来用Einsteinpy查看其克氏符的表达形式。 三维球面的度规张量可表示为 g001g11r2g22r2sin⁡…...

QML编码约定

QML中的国际化&#xff1a; QML使用以下函数来将字符串标记为可翻译的 qsTr()qsTranslate()qsTrld()QT_TR_NOOP()QT_TRANSLATE_NOOP()QT_TRID_NOOP最常用的还是qsTr&#xff08;&#xff09; string qsTr&#xff08;string sourceText&#xff0c; string disambiguation&…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...