当前位置: 首页 > 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&…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...