基础算法篇(5)(蓝桥杯常考点)—动态规划（C/C++）

动态规划

前言

在竞赛中，如果遇到动态规划的题目，只要不是经典题型，那么大概率就是以压轴题的形式出现

用动态规划解决问题的步骤:(递推形式)

1.定义状态表示:

根据经验+需要的意义，赋予dp数组相应的含义

（主要还是看需要记什么）

2.推导状态转移方程:

在dp表中分析，当前格子如何通过其余格子推导出来的

3.初始化:

将显而易见的以及边界情况下的位置填上值，来让后续填表的结果是正确的

4.确定填表顺序:

根据状态转移方程，确定按照什么顺序来填表

5.找出最终结果:

在表中找出需要的最终结果

洛谷 P10250 [GESP样题 六级] 下楼梯
洛谷 P1216 [USACO1.5] [IOI1994]数字三⻆形 Number Triangles

动态规划常要空间优化:
即把不用了的值给不要了
但是背包问题如果不能用1个数组优化，而要多个数组的话，那就不空间优化了，否则可能会超时
常见的优化方法:
方法一：一维转几个数
例题:洛谷   P10250 [GESP样题 六级] 下楼梯

方法二：二维转一维
1.是否需要修改遍历顺序
2.删掉一维即可
例题:洛谷  P1216 [USACO1.5] [IOI1994]数字三⻆形 Number Triangles

洛谷 P1115 最⼤⼦段和
洛谷 P1541 [NOIP2010 提⾼组] 乌⻳棋

一些技巧:
1.状态表示:
a.研究子数组或子序列问题时，从某个位置结尾来定义状态表示 
  例:洛谷 P1115 最⼤⼦段和
b.优化问题:有一维可以由其他维的数据推出的话，可以不要这一维(不是指那个空间优化方法)
 例题:洛谷  P1541 [NOIP2010 提⾼组] 乌⻳棋

2.状态转移方程:
a.求方案数一般是相加
b.常从最后一步开始分析去推导状态转移方程

3.初始化:
在求方案数时，一般将第一个位置初始化为1，其他位置为0

线性dp

特点：状态转移只依赖于前一个或前几个状态；状态之间的关系是线性的

路径类dp

洛谷 P1004 [NOIP2000 提⾼组] ⽅格取数

走两次的得到的值之和最大问题:
（两次的规则要一样，走到不同位置的得到的值不一样，且每位置的值只能得一次）
例题:洛谷  P1004 [NOIP2000 提⾼组] ⽅格取数
在状态表示时：两者如果是同时出发的(非同步则要改一点)，其横纵坐标之和会是一个定值
一般表示为f[st][i1][i2]:
意思是：第一条路在[i1,st-i1]，第二条路在[i2,st-i2]时，两者的路径（取数）之和最大

经典线性dp

经典线性dp问题有两个:最长上升子序列和最长公共子序列

这两道题的解题思路，定义状态表示方式和推导状态转移方程的技巧常被用到其他题目中去

洛谷 B3637 最⻓上升⼦序列
洛谷 P1091 [NOIP2004 提⾼组] 合唱队形

最长上升子序列(数据范围小时用此)
时间复杂度是O(n平方)
链接：洛谷  B3637 最⻓上升⼦序列
要理解最长上升子序列是什么意思！！！
1.状态表示:
dp[i]表示:以i位置为结尾的所有子序列中，最长递增子序列的长度
2.状态转移方程:
根据子序列的构成方式进行分类讨论:
 第一种:子序列长度为1:此时的dp[i] = 1;
第二种: 子序列的长度大于1:设j为前面某一个数的下标
只要a[j]<a[i]，i位置元素跟在j元素后面就可以形成递增序列
其dp[i] = max(dp[j]+1p,dp[i])
3.初始化:
每次填表的时候，先把这个位置的数改成最小的域值即可

主要部分的代码展示:
int ret = 0;
for(int i=1;i<=n;i++)
{ 
dp[i]=1;
for(int j=1;j<i;j++)
  {
   if(a[j]<a[i])
    dp[i] = max(dp[i],dp[j]+1); 
   }
 ret = max(ret,dp[i])
}

应用: 洛谷  P1091 [NOIP2004 提⾼组] 合唱队形

牛客网 【模板】最⻓上升⼦序列

最长上升子序列(数据范围大时用此）
时间复杂度时O(n*logn)
链接:牛客网 【模板】最⻓上升⼦序列
优化动态规划:
1.发现在考虑最长递增子序列长度时，只用关心现在长度和序列最后一个元素
因此仅需统计长度为x的所有递增序列中最后一个元素的最小值(创建数组去统计)
2.在统计过程中发现:
数组中的数呈现递增趋势，因为可以使用二分来查找插入位置
主要部分的代码展示:
for(int i =1;i<=n;i++)
{
 //处理边界情况
 if(len ==0||a[i]>f[len]) f[++len]=a[i];
else
   {
       //二分插入位置
        int l = 1,r = len;
        while(l<r)
        {
         int mid = (l+r)/2;
         if(f[mid]>=a[i]) r = mid;
         else l =mid+1;
         }
         f[l] = a[i]
    } 
 }

牛客网 ⽜可乐和最⻓公共⼦序列
洛谷 P2758 编辑距离

牛可乐和最长公共子序列
链接:牛客网  ⽜可乐和最⻓公共⼦序列
1.状态表示:
dp[i][j]表示:
s1的[1,i]区间以及s2的[1,j]区间内的所有的子序列中，最长公共子序列的长度

2.状态转移方程:
对于dp[i][j]，我们可以根据s1[i]与s2[j]的字符分情况讨论：
第一种:两个字符相同 dp[i][j] = dp[i-1][j-1]+1
第二种:两个字符不同 有以下三种策略
a.去s1的[1,i-1]以及s2的[1,j]区间内找:此时最大长度为dp[i-1][j]
b.去s1的[1,i]以及s2的[1,j-1]区间内找:此时最大长度为dp[i][j-1]
c.去s1的[1,i-1]以及s2的[1,j-1]区间内找:此时最大长度为dp[i-1][j-1]
(发现c包含在a和b情况里)
然后要a,b中的最大值即可

代码展示:
for(int i =1;i<=n;i++)
{
   for(int j = 1;j<=m;j++)
     {
       if(s[i-1] == t[j-1])f[i][j] = f[i-1][j-1]+1;
       else f[i][j] = max(f[i-1],f[i][j-1])
       }
 }


应用:洛谷  P2758 编辑距离

背包问题分类

01背包问题:没中物品只能选或不选（选0次或1次）

完全背包问题:每种物品可以选择无限次

多重背包问题:每种物品有数量限制

分治背包问题:物品被分为若干组，每组只能选一个物品

混合背包:以上四种背包问题混在一起

多维费用的背包问题:限定条件不止有体积，还会有其他因素(比如重量)

背包问题的三种限定情况:
1.体积不超过j－>小于等于j->j>=v[i]
2.体积正好为j->恰好等于j->要判断f表中某些状态是否合法
3.体积至少为j->大于等于j->j<v[i]也是合法的，映射到0位置即可

背包问题在求方案数时，要把不选的情况单独写出，然后从只选一个开始，不然套模板可能会错
例:洛谷  P1077 [NOIP2012 普及组] 摆花

洛谷 P1077 [NOIP2012 普及组] 摆花

01背包问题

牛客网 【模板】01背包
洛谷 P2946 [USACO09MAR] Cow Frisbee Team S

01背包中的最大价值问题:
模板题:牛客网 【模板】01背包
v[i]表示第i个的体积   w[i]表示第i个的价值
第一问:求这个背包至多能装多大价值的物品
 1.状态表示:
dp[i][j]表示:从前i个物品中挑选，总体积不超过j，所有的选法中，能挑选出来的最大价值
那么dp[n][v]就是我们要的结果
2.状态转移方程:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
3.初始化:无
4.填表顺序:从上往下(二维一般都是从上往下)  从右往左

代码表现:
for(int i = 1;i<=n;i++)
{ 
   for(int j=0;j<=m;j++)
    {
      f[i][j] = f[i-1][j];
      if(j>=v[i])
        f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
     }
}
空间优化版:(熟练了之后，直接写此)
   for(int i = 1;i<=n;i++)
{ 
   for(int j=m;j>=v[i];j--)//01背包空间优化要修改遍历顺序
    {
        f[j] = max(f[j],f[j-v[i]]+w[i]);
     }
}

第二问:
若背包恰好装满，求至少能装多大价值
仅需要在第一问基础上修改一下初始化以及最终结果即可
1.初始化
把所有位置先设置成-0x3f3f3f3f；然后把dp[0][0]修改成0
2.最终结果
要多一步判断最后一个位置是不是小于0

代码展现:
memset(f,-0x3f,sizeof f);//多了这个
for(int i = 1;i<=n;i++)
{ 
   for(int j=0;j<=m;j++)
    {
      f[i][j] = f[i-1][j];
      if(j>=v[i])
        f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
     }
}
if(f[n][m]<0)cout<<0<<endl;//多了这个
else cout << f[n][m]<<endl;//多了这个
空间优化版:(熟练了之后，直接写此)
memset(f,-0x3f,sizeof f);
   for(int i = 1;i<=n;i++)
{ 
   for(int j=m;j>=v[i];j--)//01背包空间优化要修改遍历顺序
    {
        f[j] = max(f[j],f[j-v[i]]+w[i]);
     }
}
if(f[m]<0)cout<<0<<endl;
else cout << f[m]<<endl;



注意:有些题可能不能用这种空间优化,因为要用到之前的数据的多少不同了
例题:洛谷  P2946 [USACO09MAR] Cow Frisbee Team S
(这题还要注意的是状态表示不能搞能力值总和为j，要搞总和模之后为j，不然空间时间都易超)

洛谷 P1164 ⼩A点菜

01背包中的方案数问题:
题目链接:洛谷  P1164 ⼩A点菜
1.状态表示:
dp[i][j]表示:从前i个菜中挑选,总价钱恰好等于j,此时的总方案数
2.针对于a[i]选或不选，分两种情况讨论:
得:dp[i][j] = d[i-1][j]+d[i-1][j-a[i]]
注意第二个状态可能不存在，要注意判断一下j>=a[i]
3.初始化:
dp[0][0] = 1

完全背包问题

牛客网 【模板】完全背包

模板题:牛客网 【模板】完全背包
第一问:求这个背包至多能装多大价值的物品
1.状态表示:和01背包一样
2.状态转移方程:
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i])
3.初始化:
从第二行开始存，第一行全初始化为0
4.没有空间优化时，是从上往下，从左往右

第二问:若背包恰好装满，求至多能装多大价值的物品
改法跟01背包那里完全相同

与01背包的不同点:在空间优化时，完全背包的遍历顺序还是从左往右

多重背包

牛客网 多重背包

例题： 牛客网  多重背包
小tip:不是所有的多重背包问题都能用二进制优化，而且优化版本的代码很长
     如果时间复杂度允许的情况下，能不优化就不优化
解法一:
1.状态表示:
dp[i][j]表示:
从前i个物品中挑选，总重量不超过j的情况下，最大的价值

2.状态转移方程:
这里不能用完全背包的方式(不是指那个空间优化)去优化
只能硬分x[i]+1种情况(选0个到选x[i]个)
选x[i]个:价值为dp[i-1][j-x[i]*w[i]]+x[i]*v[i] 

3.初始化:
全部初始化为0

4.填表顺序:
从上往下，从左往右
空间优化之后则是从右往左

代码展现:
for(int i =1;i<=n;i++)
  for(int j= m;j>=0;j--)
    for(int k = 0;k<=x[i]&&k*w[i]<=j;k++)
      f[j] = max(f[j],f[j-k*w[i]]+k*v[i])

解法二:转化为01背包问题
优化方式:用二进制将同种的x[i]个物品分组
(如果是求方案数的话，是不能用二进制去优化的，会多算几种)
把这x[i]个物品拆成一些二进制数再加上多出来的数

此题的有100种不同物品的话
如果同种的物品最多能分成5份，则数组的N要取(100+10)*5//+10纯属个人习惯

洛谷 P1077 [NOIP2012 普及组] 摆花

多重背包的方案数问题:
例题:洛谷  P1077 [NOIP2012 普及组] 摆花
也就状态转移方程和初始化改了一下

分组背包问题

洛谷 P1757 通天之分组背包

例题:洛谷  P1757 通天之分组背包
1.状态表示:
dp[i][j]表示从前i组中挑选物品，总重量不超过j的情况下，最大的价值

2.状态转移方程:
根据第i组选什么物品，可以分若干情况讨论
这个在空间优化时，第二维也要从右到左

混合背包问题

洛谷 P1833 樱花

例题:洛谷 P1833 樱花
这个混合背包的话，分情况讨论是哪种背包就是
注意的点是:多重背包和01背包的代码具有可合并性

多维费用的背包问题

洛谷 P1910 L 国的战⽃之间谍

例题:洛谷  P1910 L 国的战⽃之间谍
这无非就是多加几维就行
eg:
状态表示:
dp[i][j][k]表示:
从前i个人中挑选，伪装能力不超过j，总工资不超过k，此时能获取到的最多资料总数
eg:像这种获取到的最多资料总数，能砍到的最多的树木这种一般不为限制条件，一般是所求的值
在空间优化时，也只能优化掉第一维(从前i个人中挑选--这个一般放第一维)
空间优化后，除了第一维的遍历顺序可能都需要发生变化

区间dp

区间dp是用区间的左右端点来描述状态，通过小区间的解来推导出大区间的解

核心思想:将大区间划分为小区间，其状态转移方程通常依赖于区间的划分点

常见的划分点的方式有两个:

1.基于区间的左右端点，分情况讨论

2.基于区间上的某一个点，划分成左右区间讨论

应用：在序列中只关心左右两端，大概率用区间dp

洛谷 P1435 [IOI2000] 回⽂字串

例题:洛谷  P1435 [IOI2000] 回⽂字串
1.状态表示:
dp[i][j]表示:
字符串[i,j]区间，变成回文串的最小插入次数
那么,dp[1][n]就是我们要的结果

2.状态转移方程:
根据区间的左右端点，分情况讨论

对于区间dp的填表顺序，一般用的是:
第一维循环:从小到大枚举区间长度len;第二维循环:枚举区间左端点i,然后计算出区间右端点j
j = i+len-1 
这个len有时从1开始，有时从2开始，看题
eg:
for(int len = 1;len<=n;len++)
  for(int i = 1; i+len-1<=n;i++)

洛谷 P2858 [USACO06FEB] Treats for the Cows G/S
洛谷 P3146 [USACO16OPEN] 248 G

关于这里的状态转移方程:
1.如果划分点是基于区间的左右端点，分情况讨论
eg: 洛谷  P2858 [USACO06FEB] Treats for the Cows G/S
  先拿左边，然后去[i + 1, j] 区间获得最多的钱，
即a[i] × (n − len + 1) + dp[i + 1][j] 
  先拿右边，然后去[i,j-1]区间获得最多的钱
即a[j]*(n-len+1)+de[i][j-1]

2.如果划分点是基于区间上的某一个点，划分成左右区间讨论
eg: 洛谷    P3146 [USACO16OPEN] 248 G
  根据最后一次合并的情况，可以把区间分成[i,k][k+1,j](划分点是k)