首页 > 其他分享 >初级DP

初级DP

时间:2023-06-01 21:12:08浏览次数:47  
标签:状态 代码 位置 转移 初级 复杂度 DP

-0. DP的概念与设计和实现

概念:DP从本质上讲是图论问题的中的一种,DP的每一种状态所对应的便是一张图上的点,转移对应的便是图上的边。

如果是求最值,那便是图论中的最短路或最长路;如果要求方案数,那便是图论中的路径统计问题。

设计:DP的设计有三大要素:状态,转移方程,初始化。

实现:DP的实现通常是三种方式,从当前状态向可能状态转移,从可能前继状态向当前状态转移,记忆化搜索。通常根据实现的难易来选择。

-1. 入门DP

--1.数字三角形是一个很好的例子

我们先确定状态 \(F[i][j]\)表示到达当前位置\((i,j)\)所累积的最大的数是多少。
接下来考虑转移\(F[i][j]=max(f[i-1][j],f[i-1][j-1])+w[i][j]\).
不需初始化。
时间复杂度\(O(n^2)\) 代码

变式1.求在模100后的最大值。

当DP条件变多时,我们便考虑给DP多开一维来记录状态\(F[i][j][k]\)表示当到达位置\((i,j)\)时模\(100\)等于\(k\)是否可能\(1\)表示可能\(0\)表示不可能。
于是我们得到转移方程\(F[i][j][k]->F[i+1][j][(k+w[i+1][j])\%100]andF[i+1][j+1][(k+w[i+1][j+1])\%100]=1\)
最后扫描最后一行每一个位置\(1-k\)是否合法即可。
时间复杂度\(O(n^3)\)。

变式2.求必经某个点限制下原问题的答案。

只需先算\((1,1)\)到该点的最大值再算该点到最后一排的最大值即可。

变式3.求不经过某个点限制下原问题的答案。

只需给不能经过的点初始化一个负无穷的值即可。

--2.最长上升子序列

设计状态\(F[i]\)表示以i位置结尾的最长子序列长度
得到转移\((a_j>a_i)\)时\(F[i]=max_{j\in[1,i)]}(F[i],F[j]+1)\)
初始化F[i]=1
时间复杂度\(O(n^2)\) 代码

考虑记录方案数

新开一个g数组
点击查看代码
				if(f[j] + 1 > f[i]) { f[i] = f[j] + 1; g[i] = 0; pre[i] = j;}
				if(f[j] + 1 == f[i]) g[i] += g[j];
如果第一行执行那么第二行也必然执行 这样写才能达到我们想要的效果

考虑记录一种方案

如上方代码中记录的前继数组pre 输出时参考下述代码
点击查看代码
	/*
	ÒÔP½áβ·½°¸
	int z[], cnt;
	do
	{
		z[++ cnt] = p;
		p = pre[p];
	} while(p != 0);
	reverse(z + 1, z + 1 + cnt);
	*/

一些例题

---1.滑雪

考虑\(F[i][j]\)表示到位置\((i,j)\)最多滑雪步数
转移即为上下左右四个方向取\(max\)向当前位置转移并\(+1\)
初始化所有点为\(1\)
这样对吗? NO。 因为我们的转移需要从步数少的地方向步数多的地方转移(这类似我们要先以高度进行一个拓扑排序)然后再判断当前位置上下左右哪个位置高度大于该处才能转移到该处
时间复杂度为check ans的\(O(nm)\) 代码

---2.乌龟棋

考虑状态F[x][a][b][c][d]$为当前在x位置使用了a张1牌b张2牌...
显然x可以通过1+a+2b+3c+4d得到 于是便可以压掉
转移便是当前位置使用1或2或3或4向后转移即可
时间复杂度\(O(max种类牌数^4)\) 代码

下面介绍几种比较套路的DP

-2.区间DP

标签:状态,代码,位置,转移,初级,复杂度,DP
From: https://www.cnblogs.com/master-lio/p/17450095.html

相关文章

  • Don't Blame Me (dp问题)
    大意:有一个数组a,其中a[i]<64,问你子序列中异或值中1的个数为k的子序列个数题解:由于数组a的值很小异或后也很小,所以可以暴力dp公式:dp[i][j]//表示前i个数中异或值为j的子序列个数dp[i][a[i]&j]=dp[i-1][j]+dp[i][a[i]&j];核心:每次遍历当前a[i]与0~(1<<6)异或值的大小,更新dp......
  • 【亲测有效】wordpress多域名使用wp rocket插件问题
    wordpress多域名绑定,但是又想在主域名删除其他站缓存,这个时候在主站的默认清理按钮是无效的,只能代码方式实现。 //cleanhttp://your-site.com/contact/rocket_clean_files('http://your-site.com/contact/');//cleanhttp://your-site.com/contactandhttp://your-si......
  • Ambari2.7.5+HDP3.1.5中Yarn配置fair-scheduler
     将Yarn的调度策略修改成FairScheduler的A:找到YARN列表,然后找到yarn.resourcemanager.scheduler.class,然后将它的值进行修改,即:<property><name>yarn.resourcemanager.scheduler.class</name><value>org.apache.hadoop.yarn.server.resourcemanager.scheduler.fair.Fair......
  • 部署Ambari2.7.5 + HDP3.1.5安装
     java安装1.java解压安装cd/opttar-zxvfjdk1.8.0_181.tar.gz2.编辑环境变量配置vim/etc/profileexportJAVA_HOME=/opt/jdk1.8.0_231exportPATH=$JAVA_HOME/bin:$PATHexportCLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar3.生效环境变量配置sourc......
  • wireshark 仅抓取 DNS 报文——直接在过滤器抓包里写 udp port 53 即可
    ......
  • 扩散模型 - 简介、DDPM
    扩散模型1扩散模型(DM)扩散模型(DiffusionModel)起源于非均衡热动力学(non-equilibriumthermodynamics),是一类基于概率似然(likelihood)的生成模型。当前对扩散模型的研究主要围绕三种主流的实现:去噪扩散概率模型(DenoisingDiffusionProbabilisticModels/DDPMs)基于分数的生成......
  • 网络爬虫初级
    首先,我们来看一个Python抓取网页的库:urllib或urllib2。那么urllib与urllib2有什么区别呢?可以把urllib2当作urllib的扩增,比较明显的优势是urllib2.urlopen()可以接受Request对象作为参数,从而可以控制HTTPRequest的header部。做HTTPRequest时应当尽量使用urllib2库,但是urllib.urlre......
  • 初级数据结构--单链表
    继昨天终于明白了成功截图typedefstructLNode{ intdata; structLNode*next;}LNode;boolIsitList(LNode**Head){ *Head=(LNode*)malloc(sizeof(LNode)); if(!*Head) returnfalse; (*Head)->next=NULL; returntrue;}voidListInsert(LNode*L,intval......
  • Vulnhub: dpwwn: 1靶机
    kali:192.168.111.111靶机:192.168.111.131信息收集端口扫描nmap-A-sC-v-sV-T5-p---script=http-enum192.168.111.131爆破出mysql的root用户为空密码hydra-lroot-P/usr/share/wordlists/rockyou.txt192.168.111.131-s3306mysql-t64在mysql数据库中发现......
  • 邮局--dp经典问题
    题目:http://poj.org/problem?id=1160题意: 一些村庄被建立在一条笔直的高速公路边上,我们用一条坐标轴来描述这条高速公路,每一个村庄的坐标都是整数,没有两个村庄坐标相同。两个村庄间的距离,定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局——当然,并不是每一个村庄都......