动态规划

概述

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

一般的解题步骤

解决动态规划问题，通常由两个步骤：

1. 建立状态（阶段）定义。这个状态必须能描述一类问题的轮廓。例如在背包问题中，我们采用 dp_i,j 来表示前 i 的物品，体积不超过 j 的最优解。但是能描述一类问题轮廓的状态可能不止一种，同时，并不是每一种状态都方便转移。如何找到一种优秀的状态定义，往往是动态规划问题的难点，但这也是有一定的套路的，对于经典的dp模型，我们可以很快的定义状态，例如背包问题这一类选择类dp，又或者是递增子序列这种序列类dp，这需要我们在做题中去总结和提炼。
2. 设计状态转移。我们目前要求解的状态必须能从前面的状态转移过来，不然就无法求解。一个常见的套路就是，针对最后一个元素的决策和题目限制去设计。例如在背包问题中，对于最后一个物品，我们有选与不选两个决策。

常见的dp模型

背包DP（基础版）

01 背包

问题描述：有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

在上述问题中，每一个物品都有两种状态，选与不选。对于这种选择最优化类DP，我们常常使用dp_i,j 来表示前 i 的物品，满足条件 j 的最优解。

第 i 个物品不选，转移方程为：\(dp_{i,j} = dp_{i-1,j}\)

第 i 个物品选，转移方程为：\(dp_{i,j} = dp_{i-1,j-v_i} + w_i\)

综上，转移方程为：\(dp_{i,j} = max(dp_{i-1,j-v_i} + w_i,dp_{i-1,j})\)

同时，由于对 \(f_i\) 有影响的只有 \(f_{i-1}\) ，因此可以优化掉一维，\(dp_{j} = max(dp_{j-v_i} + w_i,dp_{j})\)，注意，如果优化掉第一维，枚举 j 的时候需要倒序枚举，避免使用同为 i 阶段的状态来更新。

完全背包

完全背包与01背包类似，区别为在完全背包中，每一个物品可以选用任意次。

采用类似于01背包的思想，决策由选与不选变为了选几个，我们可以得到状态转移方程为：$$dp_{i,j} = max^{+\infty}{k=0}(dp{i-1,j-kv_i} + kw_i,dp_{i-1,j})$$

同样的，可以优化掉一维，\(dp_{j} = max(dp_{j-v_i} + w_i,dp_{j})\)，注意，此时枚举 j 的时候需要正序枚举，由于每个物品可以任意次使用，所以可以使用同为 i 阶段的状态来任意次更新。

多重背包

与01背包类似，区别为每一个物品有\(k_i\)个。决策依旧是选与不选变为了选几个，我们可以得到状态转移方程为：$$dp_{i,j} = max^{k_i}{k=0}(dp{i-1,j-kv_i} + kw_i,dp_{i-1,j})$$

同样的，可以优化掉一维，\(dp_{j} = max(dp_{j-v_i} + w_i,dp_{j})\)，注意，此时枚举 j 的时候需要倒序枚举，因为每个物品的使用次数有限。

多重背包的二进制优化

多重背包朴素算法的时间复杂度为\(O(W\sum{k_i})\)，观察到我们可以将k个相同的物品拆分成\(log_2^k\)个大物品，可以证明这\(log_2^k\)个大物品可以组合成任意选法。时间复杂度为\(O(W\sum{log_2^{k_i}})\)

分组背包

问题描述：有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 \(v_{i,j}\)，价值是 \(w_{i,j}\)，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，决策变为选这组中的哪一个或不选。

使用dp_i,j 来表示前 i 组，满足体积不超过 j 的最优解。

综上，转移方程为：\(dp_{i,j} = max(dp_{i-1,j-v_i} + w_i,dp_{i-1,j})\)

参考代码（引用自oi wiki）：

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

线性DP（基础版）

数字三角形

问题概述：给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

这是一个典型的路径最优化DP，问题的关键在于找到一条路径，使得这条路径上的权值和最大。

对于此类问题，我们通常定义\(dp_{i,j}\)为从\((1,1)\)到\((i,j)\)的这条路径的最优解。

考虑到题目限制为只能向右下走或向左下走，所以\((i,j)\)只能从\((i-1,j)\)或\((i-1,j)\)转移，因此，状态转移方程为：\(dp_{i,j} = \max(dp_{i-1,j},dp_{i-1,j-1})+val_{i,j}\)

最长上升子序列

问题概述：给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

这是一类子序列DP问题，题目的限制为数值严格单调递增，因此我们需要在DP方程中记录当前子序列最后一个元素的数值，通常定义\(dp_i\)来表示前i的元素中，以第i的元素结尾的最优解。

可以得出，转移方程为：\(dp_i = \max_j^{j<i}(dp_j) + 1 \and val_j < val_i\)

时间复杂度：\(O(n^2)\)

最长上升子序列的贪心解法

对于不求具体的子序列，只求最长长度的最长上升子序列问题，DP法并不是最优秀的解法，有一种贪心的思想可以将时间复杂度降为\(O(nlogn)\)

下面给出贪心法求解上面问题的代码：

int main()
{
	vector<int> g;
    int n;
    cin>>n;
    for(int i = 1,x; i <= n; i ++)
    {
        cin>>x;
        if(g.empty())
        {
            g.push_back(x);
        }
        else 
        {
            int pos = lower_bound(g.begin(),g.end(),x) - g.begin();
            if(pos == g.size())
                g.push_back(x);
            else 
                g[pos] = x;
        }
    }
    cout<<g.size();
    return 0;
}

注意，如果题目要求非严格递增，则需要把lower_bound改为upper_bound！

最长公共子序列

问题概述：给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

这是一类双序列DP问题，常用\(dp_{i,j}\)表示串A前i个元素与串B前j个元素的最优解。题目的限制为公共子序列，因此我们可以通过串A和串B最后的元素是否相同来构建转移方程。

相同时，转移方程为：\(dp_{i,j} = dp_{i-1,j-1} + 1\)

不同时，转移方程为：\(dp_{i,j} = max(dp_{i-1,j},dp_{i,j-1})\)

最短编辑距离

问题概述：给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

1. 删除–将字符串 A 中的某个字符删除。
2. 插入–在字符串 A 的某个位置插入某个字符。
3. 替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

这是一类双序列DP问题，我们仍然用\(dp_{i,j}\)表示串A前i个元素与串B前j个元素的最优解。同时，串A和串B最后元素的决策题目已经给出，分别是删除、插入和替换，题目限制为将A变为B，因此，我们还是通过串A和串B最后的元素是否相同来构建转移方程。

相同时，不需要多余操作，转移方程为：\(dp_{i,j} = dp_{i-1,j-1}\)

不同时，枚举所有决策，转移方程为：\(dp_{i,j} = min(dp_{i-1,j},dp_{i-1,j-1},dp_{i,j-1})\)

注意初始化！

几道例题

例题一：(选自蓝桥：建造房屋)

分析：每一个街道有m种选择，即建造多少个房屋。根据选择类DP常见的套路而言，我们使用\(dp_{i,j}\)来表示前i条街道，预算不超过k元的最优解。对于最后一个街道来说，它的决策有m种，即让\(1\leq i\leq m\)个房屋建造到该街道上。

综上，转移方程为：\(dp_{i,j} = \sum_{k=1}^m(dp_{i-1,j-k}) \and j-k \geq i-1\)

例题二：（选自蓝桥：可构造的序列总数）

分析：首先我们可以定义\(dp_i\)用来描述当前构造的第几个数字（问题的轮廓），接下来观察题目限制，题目限制为非严格单调递增且\(a_i\)是\(a_{i-1}\)的倍数，所以我们要记录最后一个元素的数值来方便转移，观察到k的范围很小，因此我们再开一维，定义\(dp_{i,j}\)为前i个数且最后一个数为j的最优解。

其实这就是序列类DP，最长递增子序列问题的变种。因此，一定要理解基本的DP模型，很多状态定义的方法均来源于熟悉的DP模型中！

状态转移方程为：\(dp_{i,j} = \sum_{k=1}^j(dp_{i-1,k}) \and k | j\)

注意：朴素写法的时间复杂度为\(O(n^3)\)，因此我们需要预先对约数预处理。

例题三：（选自蓝桥：最快洗车时间）