【算法笔记】动态规划专题

所有解题思路已经直接整合在代码注释中。

动态规划

整体结构

条件抽象与状态描述

• 【重点1】根据题目给出的限制条件，抽象出会影响决策的部分，这个条件的数量和用法，基本上就是dp领域内题目分类的依据了。比如，单上限的一般用线性dp，双上限（双指针）的一般用二维dp，子集等条件为选不选、选几个的问题一般就归类为背包问题，需要枚举区间长度和起点来描述条件的一般归类为区间dp，等等。

• 动态规划的每一步追求的都是当前最优解，且这个最优解的结果需要被下一步“无需考虑前序实现方法”地使用，所以还要建立对当前找出的最优决策的抽象描述，或者说一个“评判的标准”。

建立递推关系（状态转移方程）

• 确定作出下一步决策所需要提供的所有信息，让上一步决策对这些信息作出传递。比如，剩余可选次数、剩余可用cost等等。

• 【重点2】枚举当前状态可做的决策选择分支，并改变上一步提供的状态信息，提供给下一步决策使用。比如，不选当前物品，除了枚举指针后移之外不做任何处理，选择当前物品，则还要减去对应的可选次数和cost，等等。

• 需要注意，在状态定义和分支决策时，都要保证互斥性，确保不会有某种决策方案被重复计算。

递推并获取answer

• 描述初始条件，从最小规模问题开始逐渐迭代直至所有状态完成计算。

• 【重点3】状态描述的定义不同，获取最终答案的方式也会不同。比如，状态是上限类时，我们想要的答案一般就是各个限制条件都达到上限时的dp值，而类似于最长上升子序列的情况，每一轮记录的决策结果（以当前元素结尾的最大长度）其实是互斥的（不可能又以a结尾又以b结尾），因此还需要对整个结果的记录进行一次遍历找出最佳答案。需要根据问题的建模来考虑answer究竟是谁，不能见到dp就直接输出dp[n]。

细分类型

线性DP

P3002 斐波那契数列

本题仅递推，不涉及决策问题。

• 【状态】

  ?dp[i];//第i项

• 【初始】

  ?dp[0] = 0;
  ?dp[1] = 1;

• 【递推】

  ?dp[i] = dp[i-2] + dp[i-1];//第i项=第i-1项+第i-2项

• 【结论】

  ?dp[n];//第n项

P5002 爬楼梯

本题仅递推，不涉及决策问题。

• 【状态】

  ?dp[i];//爬i级台阶有几种方法

• 【初始】

  ?dp[0] = 1;//爬0级1种（不爬）
  ?dp[1] = 1;//爬1级1种

• 【递推】

  ?dp[i] = dp[i-2] + dp[i-1];//爬i级=先爬i-1级再爬1级+先爬i-2级再爬2级，没有其他可能了

• 【结论】

  ?dp[n];//爬n级方法数

P5003 连续?数组最?和

本题开始涉及决策，需要进行比较，择优传入下一轮递推。

• 【状态】

  ?dp[i]//以nums[i]结尾的最大子数组和

  • 【初始】

  ?dp[1] = nums[1];//第一个元素能形成的子数组显然只有自己

• 【决策-递推】

  ?dp[i-1] + nums[i];//将当前元素接在前序子数组的后面形成新的子数组
  ?nums[i];//从当前元素开始重新建立子数组
  ?dp[i] = max(dp[i-1] + nums[i], nums[i]);//选择更好的结果进入下一轮

• 【结论】考虑在枚举过程中就完成对最大值的维护

  ?int maxSum = nums[1]; //初始化
  ?for (int i = 1; i <= nums.size(); i++) {  
  ?    dp[i] = max(nums[i], dp[i-1] + nums[i]);  
  ?    maxSum = max(maxSum, dp[i]); //若当前轮次获得了更好的结果，直接更新maxSum
  ?}

P5004 最?上升?序列

本题开始出现需要在一轮迭代中完成枚举才能确定当前最优解的情况。

• 【状态】

  ?dp[i];//以nums[i]结尾的最长上升子序列的长度

• 【初始】

  ?for(int i = 1; i <= nums.size(); i++) {
  ?    dp[i] = 1;//每个元素自身就是一个上升子序列
  ?}

• 【决策-递推】

  ?for(int i = 1; i <= nums.size(); i++) {//遍历确定的结尾项
  ? ? ?for(int j = 0; j < i; j++) {//遍历该项之前所有被存储为局部最优解的子序列
  ? ? ? ? ?if(nums[i] > nums[j]) {//判断该项能不能接在这个局部最优子序列的后面
  ? ? ? ? ? ? ?dp[i] = max(dp[i], dp[j] + 1);//存储所有可能接出来的序列中的最佳情况（或全都接不上，则从当前元素开始创建新的子序列，dp[i]保持初始状态1）
  ? ? ? ?  }
  ? ?  }
  ?}

• 【结论】需要遍历dp数组获取最大值，当然也可以和上一题一样，在枚举过程中就完成对最大值的维护，在最外层循环的循环体末尾增加更新max的逻辑即可。

P5005 打家劫舍

本题出现了不需要额外存储但是涉及决策的限制条件。

• 【状态】

  ?dp[i];//处理完前i个房子时的最大打劫金额

• 【初始】

  ?dp[0] = nums[0];//只有一个房子可以考虑的时候肯定偷
  ?dp[1] = max(nums[0], nums[1]);//前两个房子不能都偷，所以选一个更贵的偷

• 【决策-递推】

  ?for(int i = 2; i < n; i++) {//逐步增加可以考虑的房子的范围
  ? ? ?//以下二者择优
  ?    dp[i] = max(dp[i-2] + nums[i], //这间偷，前一间就不能偷，只能加dp[i-2]
  ?                dp[i-1]);//这间不偷，直接沿用dp[i-1]
  ?}

• 【结论】

  ?dp[n-1];//能考虑的房子越多，可能的结果就越好，所以所有房子都考虑的时候必定得到最优解

二维DP

P5001 数字三角形

• 【状态】

  ?dp[i][j];//从位置(i, j)到底部的最大路径和

• 【初始】

  ?for(int i = 1; i <= n; i++)
  ? ? ?dp[n][i] = triangle[n][i];//第n行所有元素本身就已经在底部，最大路径和就是自身的值

• 【决策-递推】

  ?for(int i = n-1; i >= 1; i--) {//从最后一行往上枚举
  ? ? ?for(int j = 1; j <= i; j++) {//枚举当前行所有节点
  ? ? ? ? ?dp[i][j] = triangle[i][j] + //最优路径肯定要经过当前节点
  ? ? ? ? ?//以下二者择优
  ?        max(dp[i+1][j], //左子树最优
  ?            dp[i+1][j+1]);//右子树最优
  ? ?  }
  ?}

• 【结论】

  ?dp[1][1];//显然

P5006 最?公共?序列

本题开始涉及两组数据的比较，使用双指针维护状态。

• 【状态】

  ?dp[i][j];//考虑字符串A的前i个字符与字符串B的前j个字符时计算出的LCS长度

• 【初始】

  ?for(int i = 0; i <= A.size(); i++) dp[i][0] = 0;//字符串B不参与比较，LCS必为0
  ?for(int j = 0; j <= B.size(); j++) dp[0][j] = 0;//字符串A不参与比较，LCS必为0

• 【决策-递推】

  ?for(int i = 1; i <= A.size(); i++) {//i从头到尾扫描A
  ? ? ?for(int j = 1; j <= B.size(); j++) {//j从头到尾扫描B
  ? ? ? ? ?if(A[i-1] == B[j-1]) //如果新加入的两个字符相等
  ? ? ? ? ? ? ?dp[i][j] = dp[i-1][j-1] + 1;//LCS增长一位
  ? ? ? ? ?else //在A[i-1]和B[j-1]不相等的前提下
  ? ? ? ? ? ? ?//以下二者择优
  ? ? ? ? ? ? ?dp[i][j] = max(dp[i-1][j], //考虑仅在B串加1位时的情况
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i][j-1]);//考虑仅在A串加1位时的情况
  ? ?  }
  ?}

• 【结论】

  ?dp[A.size()][B.size()];//显然，要把两个串都全考虑进去

P5007 编辑距离

• 【状态】

  ?dp[i][j];//字符串A的前i个字符转换为字符串B的前j个字符所需的最小操作数

• 【初始】

  ?for(int i = 0; i <= A.size(); i++) dp[i][0] = i;//从空串到A的前i位，需要插入i次
  ?for(int j = 0; j <= B.size(); j++) dp[0][j] = j;//同理

• 【决策-递推】

  ?for(int i = 1; i <= A.size(); i++) {//枚举
  ? ? ?for(int j = 1; j <= B.size(); j++) {//枚举
  ? ? ? ?//如果新增加的两个字符相同，意味着不需要额外处理，搞定增加前的子串就等于搞定了增加后的子串
  ? ? ? ?if(A[i-1] == B[j-1]) 
  ? ? ? ? ? ? ?dp[i][j] = dp[i-1][j-1];//不变
  ? ? ? ? ?else //如果两个字符不一样
  ? ? ? ? ? ? ?//先找出以下三者中操作次数最少的
  ? ? ? ? ? ? ?dp[i][j] = min({dp[i-1][j], //把A前i-1变成B前j，（然后插入A[i]）
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][j-1], //把A前i变成B前j-1，（然后插入B[j]）
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?dp[i-1][j-1]}) //把A前i-1变成B前j-1,（然后把A[i]变成B[j]）
  ? ? ? ? ? ?                  + 1;//加上插入或变换最后一位的操作次数
  ? ?  }
  ?}

• 【结论】

  ?dp[A.size()][B.size()];//显然，要把两个串都全考虑进去

背包问题

背包问题是一类，在满足限定条件前提下找出最优选择策略的问题，的统称。

其基本步骤依然遵循dp问题题解的整体结构，决策部分一般都是“选或不选”的问题。

P5011 0-1背包

• 【状态】

  ?dp[i][j];//考虑前i个物品，且总体积不超过j时，能够获得的最大价值

• 【初始】

  ?for(int i = 0; i <= N; i++) dp[i][0] = 0;//容量为0，什么也装不了
  ?for(int j = 0; j <= V; j++) dp[0][j] = 0;//没有物品，什么也装不了

• 【决策-递推】

  ?for(int i = 1; i <= N; i++) {//枚举可选物品数
  ? ? ?for(int j = 1; j <= V; j++) {//枚举容量
  ? ? ? ? ?if(j < weight[i-1])//这个放不下
  ? ? ? ? ? ? ?dp[i][j] = dp[i-1][j];//不放了
  ? ? ? ? ?else//能放下，则以下二者择优
  ? ? ? ? ? ? ?dp[i][j] = max(dp[i-1][j], //算算不放这个物品能拿到的最高价值
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i-1][j-weight[i-1]] + value[i-1]);//先给这个物品腾出空间，找到腾出来以后能拿到的最高价值，加上把这个物品放进去以后增加的价值
  ? ?  }
  ?}

• 【结论】

  ?dp[N][V];//考虑所有物品，且把包塞满

P5012 完全背包

状态定义、初始化和结论都和0-1背包相同，只有状态转移方程有一点区别

• 【决策-递推】

  ?for(int i = 1; i <= n; i++){
  ? ? ?for(int j = 1; j <= m; j++) {
  ? ? ? ? ?if(j < v[i]) dp[i][j] = dp[i - 1][j];
  ? ? ? ? ?else{
  ? ? ? ? ? ? ?//以下是区别
  ? ? ? ? ? ? ?for(int k = 0; k * v[i] <= j; k++){//由于物品数量不限，所以还要考虑取几个的问题，在体积允许的范围内，枚举其可能取的数量
  ? ? ? ? ? ? ? ? ?dp[i][j] = max(dp[i][j], //取k-1个以内时的最优情况
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i - 1][j - k* v[i]] + k * w[i]);//取k个时的情况
  ? ? ? ? ? ?  }
  ? ? ? ?  }
  ? ?  }
  ?}

• 【优化】

  f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....) f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

  由上两式，可得出如下递推关系：

  f[i][j]=max(f[i,j-v]+w , f[i-1][j])

  由此，我们省去第三层循环。

  ?for(int i = 1; i <= n; i++){
  ? ? ?for(int j = 1; j <= m; j++) {
  ? ? ? ? ?if(j < v[i]) dp[i][j] = dp[i - 1][j];
  ? ? ? ? ?else{
  ? ? ? ? ? ? ?dp[i][j] = max(dp[i][j],
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i][j - v[i]] + w[i]);
  ? ? ? ?  }
  ? ?  }
  ?}

P5013 多重背包

状态定义、初始化和结论也都和0-1背包相同，只有状态转移方程有一点区别

• 【决策-递推】

  ?for(int i = 1; i <= n; i++)
  ? ? ?for(int j = 0; j <= m; j++) {
  ? ? ? ? ?if(j < v[i]) dp[i][j] = dp[i - 1][j];
  ? ? ? ? ?else{
  ? ? ? ? ? ? ?//最内层循环限制条件增加了：数量在s[i]个以内
  ? ? ? ? ? ? ?for(int k = 0; k <= s[i] && v[i] * k <= j; k++)
  ? ? ? ? ? ? ? ? ?dp[i][j] = max(dp[i][j], //选k-1个以内时的最优解
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i - 1][j - v[i] * k] + w[i] * k);//选k个时
  ? ? ? ?  }
  ? ?  }
  ?}

区间DP

区间问题的枚举条件往往会涉及区间长度、区间起始点，以及对区间的分割。

P5015 石子合并

• 【状态】

  ?dp[i][j];//合并从i到j的石子的最小代价

• 【初始】

  ?for(int i = 1; i <= n; i++) dp[i][i] = 0;//就一颗不用合并

• 【决策-递推】

  从小到大枚举区间长度，使得后续计算分割点左右侧各自的合并代价时，都可以直接使用现成的数据。

  ?for(int len = 2; len <= n; len++) {//枚举区间长度，直到覆盖整个区间
  ? ? ?for(int i = 1; i <= n-len+1; i++) {//枚举区间起始点
  ? ? ? ? ?int j = i + len - 1;//计算区间中点
  ? ? ? ? ?dp[i][j] = INT_MAX;//初始化便于后续更新
  ? ? ? ? ?for(int k = i; k < j; k++) {//枚举区间分割点
  ? ? ? ? ? ? ?dp[i][j] = min(dp[i][j], //保存最好结果
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? //分割点及左侧合成一堆+分割点右侧合成一堆+合并左右两堆
  ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i][k] + dp[k+1][j] + sum[i][j]);
  ? ? ? ?  }
  ? ?  }
  ?}

• 【结论】

  ?dp[1][n];//整个区间

最优决策

P5014 股票交易

此类问题引入了新的状态描述，bool型的状态。决策时需要考虑T维持，T变F，F维持，F变T四种情况。

• 【状态】

  ?dp[i][0]；//第 i 天结束后，手头没有股票的最大利润。
  ?dp[i][1]；//第 i 天结束后，手头持有股票的最大利润。

• 【初始】

  ?dp[0][0] = 0；//开始前未持有
  ?dp[0][1] = -1e6；//开始前且持有（其实不可能，设一个特别小的值便于边界处理和更新）

• 【决策-递推】

  ?for(int i=1; i<=n; ++i){//枚举天数
  ? ? ?//当天状态为未持有
  ? ? ?dp[i][0]=max(dp[i-1][0],//前一天就未持有，什么也没干
  ? ? ? ? ? ? ? ? ? dp[i-1][1]+price[i]);//前一天持有，今天卖出，收入price[i]
  ? ? ?//当天状态为持有
  ? ? ?dp[i][1]=max(dp[i-1][1],//前一天就持有，什么也没干
  ? ? ? ? ? ? ? ? ? dp[i-1][0]-price[i]);//前一天未持有，今天买入，支出price[i]
  ?  }

• 【结论】

  ?dp[n][0];//第n天且手上已无持有