算法:计数类dp

文章目录

      • 一、举个栗子
        • 例子1:爬楼梯问题
        • 例子2:不同路径
        • 例子3:计数子序列
      • 二、基本思路
      • 三、典型例题
        • 一、ACWing:900. 整数划分
          • 1、解法一
            • 1.1、状态转移方程
            • 1.2、参考代码 O(n³) 超时
          • 2、解法二:类似完全背包问题
            • 1.1、状态转移方程
            • 1.2、解释
            • 1.3、降维优化
            • 1.4、参考代码

  计数类动态规划(Counting DP)是一种用来解决计数问题的动态规划技术,它通常用于求解在给定条件下满足某种性质的组合或序列的总数。 计数类DP问题的特点是要求计算所有可能情况的数量,而不是求最值或是否存在这样的情况。 当然我们在使用计数类dp的时候,没必要去和线性dp区分开来,会用就行。
  我们先举个栗子,来说明计数类dp是个啥,然后再来说明思路。

一、举个栗子

例子1:爬楼梯问题

  假设你在爬楼梯,每次你可以爬1个或2个台阶。给定楼梯的总台阶数n,你有多少种不同的方法可以爬到楼顶?

分析:让我们用dp[i]表示到达第i阶楼梯的方法数量。如果我们考虑最后一步,我们可以从第i-1阶跨一步到达第i阶,或者从第i-2阶跨两步到达第i阶。因此,到达第i阶的方法数是到达第i-1阶和第i-2阶方法数的和。

状态转移方程dp[i] = dp[i-1] + dp[i-2]

初始化dp[1] = 1, dp[2] = 2


例子2:不同路径

  一个机器人位于一个m x n网格的左上角,机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?

分析:定义dp[i][j]为到达网格中(i, j)位置的路径数量。要到达(i, j),机器人只能从(i-1, j)向下走,或从(i, j-1)向右走,所以dp[i][j]是这两个来源的路径数之和。

状态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化:网格的最上方dp[0][j] = 1和最左方dp[i][0] = 1,因为只有一种方式到达。


例子3:计数子序列

  给定一个字符串,计算不同的子序列个数。子序列是从给定序列中删除一些字符(也可以不删除)后形成的新序列。

分析:这个问题稍微复杂一点。我们可以使用dp[i]表示考虑到字符串的第i个字符时的不同子序列个数。对于每个新字符,它可以选择加入之前的子序列中,或者不加入。

状态转移:如果当前字符之前没出现过,dp[i] = 2 * dp[i-1]。如果当前字符之前出现过,需要减去上一次该字符出现时的子序列个数,以避免重复计数。

二、基本思路

  计数类dp的基本思路不好说,因为本质上就是要找到一个状态以及状态转移,使得满足要求计算所有可能情况的数量 并且 避免重复计算。 这也是最难得一步。

计数类DP的基本思路涉及以下几个步骤:

  1. 定义状态:根据问题的特性,合理定义状态,表示达到当前状态的可能情况数量。状态通常涉及考虑的元素个数、已选择元素的性质(如总和、最大值等)以及其他约束条件。

  2. 确定状态转移方程:根据问题的性质,确定从已知状态到未知状态的转移方式。状态转移方程描述了在当前决策下,如何通过之前的状态来计算当前状态的值。

  3. 初始化:正确初始化DP数组,特别是基础情况(通常是递归的边界条件),这些基础情况直接决定了递推的起点。

  4. 计算顺序:根据状态之间的依赖关系确定计算顺序,确保在计算某个状态之前,它依赖的状态已经被计算。

  5. 结果汇总:根据问题要求,从DP数组中提取最终结果。有时可能需要遍历DP数组的某些部分来汇总最终的计数结果。

三、典型例题

一、ACWing:900. 整数划分

900. 整数划分
在这里插入图片描述
  这类问题的难点再于找到状态和状态转移方程,以及看出来它是一个动态规划题。

1、解法一

用题目本身最接的方式去思考:
  对于数n和 数 n+1的划分方法有没有关系?我们定义dp[i]表示数字i的不同划分方法,那么dp[n+1]dp[n]的关系是什么?在直观上考虑n+1n在大小上相差1,因此n+1n的划分关系是:

  • n+1n多了一种n+1本身
  • n+1将1拿出来,剩下的等同于n的划分
  • 拿出来的1,可以与n的某些划分的中的数合并,可以得到新的划分。我们来考察n+1的划分
    • n+1(n,1) , (n-1,2) , (n-2,3) , (n-3,4) , (n-4,5) ···((n+1)/2,(n+1)/2) ,其中()表示一种划分,括号中的前一个数是怎么划分的不管,后一个数就是一个确切的数,并且满足,前一个数的划分的最后一个数≥后一个数。对于n而言,很显然这些划分对于n中都是没有的。因为我们单独枚举了n+1的最后一个数,那么留给前面的数尽管可能在n中存在这样的序列,但是加上了n+1枚举的最后一个数 就不可能存在这样的序列了。这样问题就出现了,我们怎么才可能找到到底有多少种?
      因此既然有问题,我们不妨将关系定义为二维:dp[i][j]表示 数字i的划分中 以 j结尾的划分数量,那么可以定义数字i的划分数量dp[i][0]等于dp[i][1]加到dp[i][i]。那么我们就可以解决了~

  实际上当我们定义为二维的时候,我们就可以发现,我们实际上是枚举划分的最后一个位置来分类讨论求解,在分类讨论时,我们将当时的状态数存下来以便于后续转移!

1.1、状态转移方程
  • 初始化dp[i][i]=dp[i][0]=1,表示i本身这种划分。
  • dp[i][j]+=dp[i-j][m]:其中j>1&&j<=i-j并且m>=j,并且m<=i-j (i-j , j)
  • dp[i][1]=dp[i-1][0](减少计算)
1.2、参考代码 O(n³) 超时
#include<bits/stdc++.h>
using namespace  std;
int dp[1001][1001];//不存在的情况划分数为 0
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N;cin>>N;dp[1][0]=dp[1][1]=1;int p=1e9+7;for(int i=2;i<=N;++i){dp[i][i]=1;//i的情况dp[i][1]=dp[i-1][0];dp[i][0]=(dp[i][i]+dp[i][1])%p;//全1的情况for(int j=2;j<=i/2;++j){//i的划分中 以j为尾数for(int m=j;m<=i-j;++m){//遍历i-j中满足条件的所有可能情况,至少要以j结尾dp[i][j]=(dp[i][j]+dp[i-j][m])%p;//只需要i-j的划分以m>=j结尾就行,当然m>i-j就无意义了。}dp[i][0]=(dp[i][0]+dp[i][j])%p;//累计数量}}cout<<dp[N][0];return 0;
}
2、解法二:类似完全背包问题

链接:完全背包问题解析
转化问题去思考:
  我们很容易想到的一个点是,实际上我们在划分时,只需要划分的数字集合不一样就行了,也就是数字集合的总和能达到n就行了,而不需要满足所谓的n1>=n2>=n3···这种形式上的顺序要求。那么这个问题就转化成了一个类似完全背包的问题了:

  • 对于1~n,n个数字想象成n个物品,体积大小就是数字大小,物品可以无限次被装
  • 一个背包只能装满总体积为n的物品

这个问题就完全被转化成为一个完全背包问题,求体积为n的背包有多少种不同的装物品的情况。

在这里插入图片描述
而这里转化为求:目标是达到背包最大承重的情况下,选取物品可以无限次,选取物品的不同种类数。

本题和完全背包问题的区别,就变成了是求最大利益,还是求种类数。

1.1、状态转移方程

定义 dp[i][j]表示考虑前i个物品,物品不限量装满体积为j的背包时,可以装物品的不同情况数。
一般的:

for(int i=1;i<=n;++i)//遍历物品
for(int j=0;j<=n;++j)//遍历体积
for(int k=0;k*i<=j;++k)//遍历物品承装次数dp[i][j]+=dp[i-1][j-k*i];//物品i可以考虑 k 次

但实际上,根据以上推导可以发现,当考虑前i个物品时,体积为j-i的背包的所有可能情况,加一个物品i,就对应于背包体积为j至少有一个物品i所能对应的所有情况了(因为根据以上循环可知,j-i背包的所有可能情况,包含了没有物品i的情况,以及包含了能有则有物品i的情况,那么将其转移至j背包,j背包就包含了至少有一关i物品所能对应的所有情况了)。优化相当于合并情况,避免重复计算。

  • 不加入物品i时种数:dp[i-1][j]

  • 加入物品i但不限次时种数:dp[i][j-i]

  • dp[i][j]=dp[i-1][j]+dp[i][j-i]

1.2、解释
  1. 不加入物品i时的种数:dp[i-1][j]
  2. 加入物品i但不限次数时的种数:dp[i][j-i]

对于这两个状态转移方程,它们分别代表了以下含义:由于一个包含i,一个不包含i,这两种划分必然是互不包含的。

  1. dp[i-1][j]:这表示考虑前i-1种物品(或者说数字),使得整数划分的总和为j的方法数量。在这个状态中,我们不包括i个物品(或者说数字i),即我们看不包含i能划分成j的种数。

  2. dp[i][j-i]:这表示考虑前i种物品(或者说数字),其中至少包含一个i,使得整数划分的总和为j的方法数量。由于我们考虑的是完全背包问题,即每个数字可以被无限次使用,所以在当前状态下加入i后,总和为j-i的状态可以直接转移到总和为j的状态。简单地说,dp[i][j-i]就是考虑j-i总和时,还能继续加入i以到达j的种数,且这种情况情况至少包含了一个i,即j-ij的转移,而其余数量的i包含在j-i的划分中。

将这两个状态结合起来,我们得到整数j的总的划分方法数量:

dp[i][j] = dp[i-1][j] + dp[i][j-i]

这个方程结合了两种情况:一种是不包含数字i的划分种数,另一种是至少包含一个数字i的划分种数。这两种情况构成了所有可能的情况。

为了清晰起见,假设我们有一个整数划分问题,要将数字5分解为不大于5的整数之和。使用上面的状态转移方程:

  • 如果我们不使用数字5,那么dp[5][5]需要包含不使用5得到5的所有方法,即dp[4][5]
  • 如果我们至少使用一个5,那么我们看在不超过5的情况下,有多少种方法得到0,这是一个空划分,只有一种方式,所以dp[5][5]还要加上dp[5][0]

这样,dp[5][5]就等于dp[4][5](不使用5的方法)加上dp[5][0](至少使用一个5的方法)。当然,dp[5][0]在这种情况下是1,因为只有一种方法用5得到5

这就是为什么整数划分问题在考虑加入物品(或数字)时使用的是dp[i][j-i],它反映了完全背包中的无限使用特性。

1.3、降维优化

背包问题降维优化是很简单的,因为每次使用只使用之前的,因此可以降维:

for(int i=1;i<=n;++i)//遍历物品ifor(int j=i;j<=n;++j)//遍历背包大小,从小到大遍历,因为dp[i][j]可以由dp[i][j-i]转移,因此小j需要先计算出来。dp[j]=(dp[j]+dp[j-i])%p;
cout<<dp[n];
1.4、参考代码
#include<bits/stdc++.h>
using namespace  std;
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N;cin>>N;int dp[1001]={};dp[0]=1;int p=1e9+7;for(int i=1;i<=N;++i){for(int j=i;j<=N;++j)dp[j]=(dp[j]+dp[j-i])%p;}cout<<dp[N];return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/305075.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言——详解字符函数和字符串函数(二)

Hi,铁子们好呀&#xff01;之前博主给大家简单地介绍了部分字符和字符串函数&#xff0c;那么这次&#xff0c;博主将会把这些字符串函数给大家依次讲完&#xff01; 今天讲的具体内容如下: 文章目录 6.strcmp函数的使用及模拟实现6.1 strcmp函数介绍和基本使用6.1.1 strcmp函…

消息队列之-----------------zookeeper机制

目录 一、ZooKeeper是什么 二、ZooKeeper的工作机制 三、ZooKeeper特点 四、ZooKeeper数据结构 五、ZooKeeper应用场景 5.1统一命名服务 5.2统一配置管理 5.3统一集群管理 5.4服务器动态上下线 5.5软负载均衡 六、ZooKeeper的选举机制 6.1第一次启动选举机制 6.2非…

uniapp极光推送、java服务端集成

一、准备工作 1、进入【服务中心】-【开发者平台】 2、【创建应用】&#xff0c;填写应用名称和图标&#xff08;填写项目名称&#xff0c;项目logo就行&#xff0c;也可填写其他的&#xff09; 3、选择【消息推送】服务&#xff0c;点击下一步 ​ ​ Demo测试 参照文档&…

第15届蓝桥STEMA测评真题剖析-2024年3月10日Scratch编程初中级组

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥杯真题&#xff0c;这是Scratch蓝桥杯真题解析第180讲。 第15届蓝桥第5次STEMA测评&#xff0c;这是2024年3月10日举办的STEMA&#xff0c;比赛仍然采取线上形式。这…

达梦关键字(如:XML,EXCHANGE,DOMAIN,link等)配置忽略

背景&#xff1a;在使用达梦数据库时&#xff0c;查询SQL中涉及XML,EXCHANGE,DOMAIN,link字段&#xff0c;在达梦中是关键字&#xff0c;SQL报关键词不能使用的错误。 解决办法&#xff1a; 配置达梦安装文件E:\MyJava\dmdbms\data\DAMENG\dm.ini 忽略这些关键词&#xff0c;…

【Linux】shell 脚本基础使用

在终端中输入命令可以完成一些常用的操作&#xff0c;但是我们都是一条一条输入命令&#xff0c;比较麻烦&#xff0c;为了解决这个问题&#xff0c;就会涉及到 shell 脚本&#xff0c;它可以将很多条命令放到一个文件里面&#xff0c;然后直接运行这个文件即可。 shell 脚本类…

Jupyter Notbook如何安装配置并结合内网穿透实现无公网IP远程连接使用

文章目录 推荐1.前言2.Jupyter Notebook的安装2.1 Jupyter Notebook下载安装2.2 Jupyter Notebook的配置2.3 Cpolar下载安装 3.Cpolar端口设置3.1 Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&am…

分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测

分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测 目录 分类预测 | Matlab实现KPCA-IDBO-LSSVM基于核主成分分析和改进蜣螂优化算法优化最小二乘支持向量机分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述…

炒股自动化:交易接口API才是重点,券商官方散户可用的接口

上一篇我们用get_full_tick取到了数据&#xff0c;也讲了变量和字典的基本概念&#xff0c;这次我们向交易所发送订单试试。前面文章的链接放在文末了&#xff0c;需要的可以看一下 这些内容是给新手看的&#xff0c;找接口的大佬们直接拉到文末即可 取市场数据的方法很多&am…

【MATLAB源码-第12期】基于matlab的4FSK(4CPFSK)的误码率BER理论值与实际值仿真。

1、算法描述 4FSK在频移键控&#xff08;FSK&#xff09;编码的基础上有所扩展。FSK是一种调制技术&#xff0c;它通过在不同频率上切换来表示不同的数字或符号。而4FSK则是FSK的一种变种&#xff0c;表示使用了4个不同的频率来传输信息。 在4FSK中&#xff0c;每个数字或符号…

ONERugged车载平板电脑厂家丨工业车载电脑优势体现丨3年质保

作为现代社会中必不可少的出行工具&#xff0c;汽车不仅仅是代步工具&#xff0c;更是我们生活中的重要一部分。而在如此多功能的汽车内&#xff0c;一款高可靠性、适应不同行业应用的车载平板电脑成为了当下的热门选择。ONERugged车载平板电脑以其卓越的品质和强大的功能而备受…

post请求搜索功能爬虫

<!--爬虫仅支持1.8版本的jdk--> <!-- 爬虫需要的依赖--> <dependency> <groupId>org.apache.httpcomponents</groupId> <artifactId>httpclient</artifactId> <version>4.5.2</version> </dependency>…

git配置多SSH

目的&#xff1a; 一台电脑可以让github、gitee等账号同时存在&#xff0c;让不同账号配置不同的密钥 第一步&#xff1a;创建不同平台的SSH公钥 执行命令&#xff1a; ssh-keygen -t rsa -C "对应仓库邮箱地址" -f ~/.ssh/id_rsa.github 如果执行上面的命令&…

头歌机器学习实验 第7次实验 局部加权线性回归

任务描述 本关任务&#xff1a;编写一个利用局部加权计算回归系数的小程序。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a;1.局部加权算法的思想&#xff1b;2.局部加权的核心算法。 局部加权算法的思想 在局部加权算法中 &#xff0c;我们给待预测点附近…

探索设计模式的魅力:MVVM模式在AI大模型领域的创新应用-打破传统,迎接智能未来

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 MVVM模式在AI大模型领域的创新应用-打破传统迎接智能未来 &#x1f680; “在人工智能的领域里&a…

08 - 镜像管理之:镜像仓库harbor介绍

本文参考&#xff1a;原文1 1 Harbor仓库介绍 Docker容器应用的开发和运行离不开可靠的镜像管理&#xff0c;虽然Docker官方也提供了公共的镜像仓库&#xff0c;但是从安全和效率等方面考虑&#xff0c;部署我们私有环境内的Registry 也是非常必要的。 之前介绍了Docker私有仓…

CSS设置文本

目录 概述&#xff1a; text-aling: text-decoration: text-transform: text-indent: line-height: letter-spacing: word-spacing: text-shadow: vertical-align: white-space: direction: 概述&#xff1a; 在CSS中我们可以设置文本的属性&#xff0c;就像Word文…

解压文本(dfs+判环)

思路&#xff1a; 不难发现文件可以解压&#xff0c;当且仅当 1 号点出发能到达的节点集合&#xff0c;是一个有向无环图&#xff08;DAG&#xff09;。 无法解压的情况&#xff0c;就是图里存在环。于是我们可以 dfs 解压到这个文本时&#xff0c;给其标记 vis[i] true&…

YOLOv8 推理脚本--置信度保留多位浮点数 特征图可视化

效果 特征图可视化: 4位浮点数: 原始2位浮点数4位浮点数推理 --detect.py 说明 在进行改动前,请大家先阅读下 基础入门篇 | YOLOv8 项目【训练】【验证】【推理】最简单教程 | YOLOv8必看 | 最新更新,直接打印 FPS,mAP50,75,95 ,确保会用我给的推理脚本。 YOLO( ):…

关于01背包和完全背包问题的细节思考

01背包问题 #include<iostream> #include<stdlib.h> #include<vector> #include<cmath> int main() {int M0; //材料数int N0; //背包容量std::cin>>M>>N;std::vector<int>space(M,0);for(int i0;i<M;i) std::cin>>…