DP-PPT

- 2 mins read

简单DP

writingdog

目录

  • 什么是DP
  • DP怎么写
  • 例题

DP的简单描述

DP是适用于一类问题的解题策略。 问题往往需要输出一个东西的存在性、次数或者最大/最小值，但不需要给出具体的方案。

一种 或许可行 的思路是：给问题划分范围，解决这个问题的较小范围版本，由此算出这个问题的答案。（前i个 -> 前i+1个）【子问题和原问题】

能够联想到递推和递归：可以先写出初态，然后用for循环不断推，直到推出答案。也可以不断从大问题递归到小问题，直到到达可确定的初态。 【DP的两种写法】

状态

如何从小范围问题推向大范围问题？ 需要存下来小范围问题结果的某些信息，以此计算得到大范围的相同类型的信息。 这些信息（称为状态）应该能够刻画问题的特征 【DP的状态设计】 应该存在确定的计算方式，能从小范围问题的状态算出大范围问题的状态 【DP的转移方程】

如何高效计算？ 只存储、处理我们需要的（最优）信息，减小复杂度。

状态大多用数组存储，也存在更复杂的方式，比如 F - Fighter Takahashi (atcoder.jp) F-来点每日一题_2024牛客寒假算法基础集训营4 (nowcoder.com)

一个例子

给一个 $n\times m(2 \leq n,m \leq 10^2)$ 的网格，一开始在左上角 $(1,1)$ ，每一步只能向右或向下走，不能经过 ‘#’ 格子，求走到右下角 $(n,m)$ 有多少种走法。

原问题：到(i,j)有几种走法 子问题：到(i-1,j)，到(i,j-1)有几种走法

用dp[i][j]表示到$(i,j)$的走法数，答案是dp[n][m]。 可得转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]。 (二重for循环，i从小到大，j从小到大) 对 ‘#’ 格子，将对应的dp[i][j]赋为0。

问题特征

能用动态规划解决的问题有以下几个特征。

  • 子问题重叠 子问题是原大问题的小版本，解决方法完全一样,但范围、规模更小。计算大问题时，需要知道子问题的解。 把大问题拆成小问题

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

  • 最优子结构 大问题的最优解包含小问题的最优解，可以从小问题的最优解推出大问题的最优解。

  • 无后效性 已经求解的子问题，不会再受到后续决策的影响。 只需要考虑子问题的状态，不需要知道经过什么步骤到达这个状态。

基本思路

动态规划分为几步：

  1. 将原问题划分为若干子问题，提取这些子问题的特征（称之为 状态），用状态描述问题；
  2. 寻找每一个状态的可能 决策，写 状态转移方程。
  3. 写程序实现

转移写法

  • for循环（递推）
for(int i=1;i<=n;++i)
{
	for(int j=1;j<=m;++j)
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
}

填表法 ：当前点的状态，根据状态方程，根据之前点的状态推导出来。 刷表法：由当前点的状态，更新其他点的状态。

  • 记忆化搜索（递归）
int dp[N][M];
int dfs(int i,int j)
{
	if(i==0||j==0)//边界
		return 0;
	if(dp[i][j]!=0)//已经算过
		return dp[i][j];
	return dp[i][j]=max(dfs(i-1,j),dfs(i-1,j-1));//转移，储存
}
cout << dfs(n,m);

实现

考虑时间、空间复杂度，可能要在初步思路上优化

  • 状态： 刻画子问题的特征
    • 准确，充分
    • 精简状态，控制状态数数量级在1e8内
  • 转移写法：
    • 一般写递推，如果递推很难写，试试记忆化搜索（会慢一点）
    • 如果直接暴力转移复杂度太高，再尝试优化

比如用前缀和优化，对$f[i]=\Sigma_{a[i]\leq j<i}{f[j]}$，($1 \leq a[i] < i$)，如果直接算是$O(n^{2})$的， > cpp > for(int i=1;i<=n;++i) > { > for(int j=a[i];j<i;++j) > { > f[i]+=f[j]; > } > } > > 如果在转移的同时算一下前缀和，是$O(n)$的， > cpp > for(int i=1;i<=n;++i) > { > f[i]=sum[i-1]-sum[a[i]-1]; > sum[i]=sum[i-1]+f[i]; > } >

这个例子是随便举的（）

例题

frog2

河面上有$N(2 \leq N \leq 10^5)$块石头。有一只青蛙在第$1$块石头上，它想跳到第$N$块石头上。

青蛙一次最多只能跳过$K(1 \leq K \leq 100)$块石头。从第$i$块跳到第$j$块需要花费青蛙$abs(h_i - h_j)$的体力$(1 \leq h_i \leq 10^4)$。求青蛙到达第$N$块石头所耗费的最小体力值。

5 3
10 30 40 50 20

最优化问题

用dp[i]表示到达第$i$块石头所耗费的最小体力值。

$dp[i]=min(dp[j]+\lvert h[i]-h[j] \rvert),(0,i-x \leq j \leq i-1)$

赋初值 dp[1]=0
循环 i 2->n
  循环 j max(0,i-k) -> i-1
答案dp[n]

滑雪

Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。 区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24-17-16-1$（从 $24$ 开始，在 $1$ 结束）。当然 $25$－$24$－$23$－$\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。

对于 $100%$ 的数据，$1\leq R,C\leq 100$。

定义dp[i][j]为以$(i,j)$结尾滑坡的最长长度，最短为1， 从相邻且更高的点转移得到，长度加1取最大值。

记忆化搜索，时间复杂度是总状态数$O(n*m)$。

经典的01背包

有N件物品和一个容量是V的背包。第 i 件物品的体积是 vi，价值是 wi。

对每件物品，可以选择是否放入背包，每件物品只能使用一次。要求物品的总体积不超过背包容量。

求背包能装物品的最大总价值。

让v<=V且m尽量大。

这里只是求一个答案，不需要对应的具体方案（哪些选，哪些不选）。所以对一个选择方案，只需要关心它的总体积v和总价值m。

要素有：物品数量n，物品总体积v，总价值m。

【问题状态设计】

对n个物品，要求是： v<=V, 而且 对确定的v，m最大 或 对确定的m， v最小。

可以用dp[v]保存总体积<=v时得到的最大价值。dp[V]就是所求答案。

也可以dp[m]保存总价值为m时占用的最小空间。找到最大的i，使dp[i]<=V，i即为答案。

为什么dp[v]对应的是<=v，而非=v时的最大价值：因为有可能最优方案装不满V，只能装到V-1,V-2之类。此时用dp[V]就能统计到这种情况。

用DP的术语来说，原问题对应在n件物品中选择的情况，子问题就是n-1件物品选择的情况。可以从子问题一步步推到更大的问题，直到推到原问题。

用dp[v]保存总体积<=v时得到的最大价值。dp[V]就是所求答案。

记dp[i][j]为在前i件物品中选择，选中体积最多为j的方案，获得的最大价值。

转移方式： dp[i][j]=dp[i-1][j] (j<v[i]) dp[i][j]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j])，(j>=v[i])

已知考虑前i-1件物品获得的最优情况和第i件物品的信息(dp[i-1]和v[i],w[i]) ，dp[i][j]可以从两种途径获得，第一是选择第i件物品时，从dp[i-1][j-v[i]]+w[i]转移得到，第二是不选第i件物品时，从dp[i-1][j]转移得到。对于两种答案取最优值储存。

总的状态数是$O(n\times{V})$ 转移时，复杂度为$O(n\times{V})$。

整个过程的复杂度是$O(n\times{V})$。

初始化时，将dp全赋为0即可。 dp[0][0]可以被视为是dp的起点。

dp[i][m]保存在前i个物品中选取，总价值为m时占用的最小空间。

初始化时赋为INF

dp[i][m]=dp[i-1][m],(m<w[i]) dp[i][m]=min(dp[i-1][m],dp[i-1][m-w[i]]+v[i]),(m>v[i])

总的状态数是物品数*总价值$O(n\times\Sigma{w_i})$ 复杂度也是如此

CF577B Modulo Sum

给出长度为n的序列a和整数m，求是否存在一个非空的a的子序列，满足该子序列的和能为m所整除。  (1 ≤ n ≤ 1e6, 2 ≤ m ≤ 1e3, 0 ≤ $a_i$ ≤ 1e9)  时限 2s，空间 256mb    子序列不是连续的: 可以在n个数中选数，每个数或者选或者不选，问能不能选到数的总和模m为0。

   已经选了一些数，再选新的数时，就能从选之前的数模m的可能性推出现在选或不选这个数后得到的模m的结果。以这种方式递推。    定义dp[i][j]表示在前i个数中选数，总和模m等于j的情况是否存在（0为不存在，1为存在）。   如果dp[i-1][j]==1，考虑a[i]选不选，选则dp[i][(a[i]+j)%m]=1，不选则dp[i][j]=1。转移时这样写就可以：

  dp[i][(a[i]+j)%m]|=dp[i-1][j];
  dp[i][j]|=dp[i-1][j];

这样要开dp[n][m],有$O(nm)$个状态，每个状态的转移是$O(1)$的，总时间复杂度为$O(nm)=O(10^9)$。状态数本身就太多了。

如果n>=m，一定能选出符合要求的子序列。 (考虑前缀和)

在n<m时，再执行前面的动态规划过程，此时$O(nm)\leq O(m^2)$个状态，总时间复杂度也是$O(m^2)$。