C++算法与数据结构

动态规划 最优化问题

生活中我们常常遇到这样一些问题：

• 举例——接水问题
  • 有n个人，每个人接水时间为 t i t_i ti​，现在只有一个水龙头，请问如何安排n个人的顺序，使得每个人的平均等待时间最少？
• 举例——旅行商问题
  • 给定n个城市，两两城市之间都有公路连接，并且连接ii城市和j城市之间的公路距离为 w i , j w_{i, j} wi,j​。现有一个旅行商，希望从一个点出发，经过所有城市，再回到起始点。并且，旅行商只愿意经过每个城市一次。请问整个过程的最短距离是多少？
• 举例——背包问题
  • 给定n个物品，每个物体有个体积 v i v_i vi​和一个价值 p i p_i pi​。现有一个容量为V的背包，请问如何选择物品装入背包，使得获得的总价值最大？

看到上面的例子，我们发现这些问题都是在最大化（或者最小化）某个指标：最小化平均等待时间、最小化总旅行路程、最大化背包里的物品个数。这种类型的问题我们一般称为最优化问题。

• **最优化问题（optimization problem）**是在一些约束下，通过进行一些决策，使得最终获益最大（或损失最小）的一类问题。

数字金字塔问题

观察下面的数字金字塔：

现在，需要我们找到一种方法，查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。

• 注：每一步可以走到左下方的点也可以到达右下方的点。

比如，在上面的样例中，从 7→3→8→7→5的路径经过数字的和最大。

现在，我们把数字金字塔转化成一个算法问题，就变成了：

• 给定一个n层的金字塔，求一条从最高点到底层任意点的路径使得路径经过的数字之和最大。
• 注：每一步可以走到左下方的点也可以到达右下方的点。

基本思路

我们按照下面的步骤依次观察这个问题的结构：

1. 首先，因为我们可以走到最下面一层的任意点。那么，只要我们能够分别求出到达每个点的最大路径，然后在所有点里面取最大值即可解决这个问题。

2. 下面我们仅考虑走到最下面一层确定点的最大路径。假设我们现在想求走到最下面一层中间的2的最大路径，最暴力的方法就是列举所有走到2的路径，然后取路径和最大的一条作为答案。所以，所有走到2的路径如下：

   (7→3→8→7→2)  7+3+8+7+2=27
   (7→3→1→7→2)  7+3+1+7+2=20
   (7→3→1→4→2)  7+3+1+4+2=17
   (7→8→1→7→2)  7+8+1+7+2=25
   (7→8→1→4→2)  7+8+1+4+2=22
   (7→8→0→4→2)  7+8+0+4+2=21
   

   所以，最终走到2的路径里面，数字和最大是27。

3. 我们进一步观察所有走到2的路径。因为它的路径只可能从上面两个方向走下来。所以如下图，所有走到2的路径可以被分成两类：从7走过过来的路径和从4走过来的路径。

4. 对于所有结尾是7的路径

   (7→3→8→7)   7+3+8+7=25
   (7→3→1→7)   7+3+1+7=18
   (7→8→1→7)   7+8+1+7=23
   

   我们只需要接上一段→2，就可以变成从最上面的结点走到2的路径：

   但是，如果我们已经知道“到达7的路径”里面第2条路经和第3条路径不如第1条路径，是不是就可以直接舍弃下面两条，只考虑经由第1条路径走到2的情况？也就是说，为了求所有“经由7走到2”的路径里面，我们只需要计算下面一条路径即可：

   (7→3→8→7→2)   7+3+8+7+2=27
   

   同样，对于所有“经由4走到2”的路径里面，我们也只需要挑选到达4最大的一条，然后将→2接在后面。

   (7→8→1→4→2)   7+8+1+4+2=22
   

5. 那么因为“从三角形顶端到达2”的路径里面，只有上面两种情况，所以，它们之间的的较大值就是到达2的最大路径，也就是
   m a x { 27 , 22 } = 27 max\{27,22\}=27 max{27,22}=27

6. 如此一来，我们不需要枚举所有”从顶点到达2“的路径。但为了找出两种情况下各自的最大值，我们仍需要枚举”从顶点到达7“和”从顶点到达4“的路径。

   但是，我们发现，找到”从顶点到达7“和”从顶点到达4“的最大路径，就是一个和原问题”从顶点到达2“结构相似的问题！另外，由于7和4的位置比2要少一行，所以实际上，这两个问题是一个规模更小的问题！也就是说，这两个问题是原问题的一个子问题！那么，我们利用和上面类似的分析思路，就可以不用枚举所有到达7和4的路径了。

数字金字塔问题算法描述

这里，我们把上一步的基本思路形式化成一个严谨的算法：

1. 我们用a[i][j]存储数字金字塔第i行第j列的数字，用f[i][j]表示”从顶点到达第i行第j列“的所有路径中最大的数字和。
2. 对于顶点，因为它是起始点，所以f[1][1] = a[1][1]。
3. 因为到达(i, j)的路径最多只可能从(i - 1, j - 1)和(i - 1, j)两个点走过来（如果在三角形的最左边或者最右边，那么它的上一个结点就只有一种情况），所以，我们有下面的关系：

   f[i][j] = f[i - 1][j - 1] + a[i][j]    ；                    // i == j
   f[i][j] = f[i - 1][j]     + a[i][j]    ；                    // j == 1
   f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i] [j]；  // otherwise
   

   那么，观察这个等式，会发现如果我们已知f[i - 1][j - 1]和f[i - 1][j]，就可以求出f[i][j]。所以实际上，它有点像一个特殊形式的递推：有初始状态和递推关系。那么我们通过一个二重循环就可以求出所有f[i][j]。
4. 最后，我们输出所有f[n][j]对于所有(1<=j && j<=n)的最大值即可。

代码实现

#include 
#define N 1005
#define M 110
using namespace std;

int n;

int a[N][N], f[N][N];

int main() {
    // 输入
	cin >> n;
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= i; ++j)
			cin >> a[i][j];
			
    // 动态规划过程
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= i; ++j)
			f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
    		// 此处没有讨论 j == 1 和 i == j 的情况
    		// 是因为当 j == 1 时，f[i - 1][j] == 0
    		// 是因为在数字金字塔所有数字都是正数的情况下
    		// max函数一定不会选择用f[i - 1][j]来转移
    		// i == j 的情况同理
			
    // 输出
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans = max(ans, f[n][i]);	// 求第n行的最大值
	cout << ans << endl;
	
	return 0;
}

复杂度分析

• 空间复杂度
  • 该问题的空间复杂度是O(n^2)。
• 时间复杂度
  • 动态规划因为大部分都是由一些for循环组成，所以复杂度分析相对简单。在本例中，因为有两层for循环，并且都是n左右的数量级，所以整个算法的复杂度为O(n^2)。

动态规划分析流程和条件 分析流程

在数字金字塔的分析中我们发现，用动态规划解决问题的过程，就是一个把原问题的过程变成一个阶段性决策的过程。

比如在数字金字塔问题中，路径每往下延伸一行，我们就进行到下一个阶段，或者步骤。而在每一个步骤里，我们需要决策到底是从左上过来，还是从右上过来。在运用动态规划方法分析问题的过程中，下面四个要素是要明确的：

1. 状态。状态用于描述每一个步骤的参数以及结果。在数字金字塔的例子中，每个f[i][j]表示的就是一个状态。其中数组下标是当前路径的结尾，而值是以i行j列元素为结尾的所有路径中的最大值。
2. 转移方程。转移方程用于描述不同状态之间的关系。在上面的例子中，f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]就是一条转移方程。它描述了结尾为下一行的第j个结点的路径，和以上一行第j-1个结点和第j个结点路径之间的关系。
3. 初始状态。初始状态描述的是整个转移方程推导的开始，是不需要经由别的状态就知道结果的状态。上面的例子中，f[1][1]=a[i][j]就是初始状态。我们以这个状态为起点，最终推导出整个三角形上每一个位置的答案。
4. 转移方向。转移方向描述的是推导出不同状态的解的先后关系。我们之所以要明确转移方向，是因为我们不希望"已知B状态只能由A状态推到过来。但是当我们想推导B时，发现A状态的结果我们还不知道”类似的事情发生。比如由转移方程中f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]，我们发现，如果想推导f[i][j]，必须先推导f[i - 1][j - 1]和f[i - 1][j]。所以，按照i从小到大，j从小到大的顺序推导是一种可行的推导方向。

动态规划条件

那么，是不是所有最优化类问题都能用动态规划来解决呢？

不是。

那么，使用动态规划需要满足什么条件？

在这里指出，用动态规划求解要求我们设计出状态和转移方程，使得它们满足下面三个条件：

1. 最优子结构：原问题的最优解，必然是通过子问题的最优解得到的。比如上面的例子中，我们提过，如果所有以7为结尾的路径里面，有一条的数字和最大。那么，在所有经由7到达2的路径里，我们一定选择到达7的和最大的一条。所以，这样的问题具有最优子结构的性质。

2. 无后效性：前面状态的决策不会限制到后面的决策。比如说数字金字塔问题里，无论以任何方式走到7，我们都可以在后面接一段从7走到2，变成一条到达2的路径。所以，数字金字塔没有后效性。但是，在旅行商问题里，如果我们从1号城市开始，走到3号城市，那么途中经没经过2号，将会影响到3号城市后面的路径。这个场景就是有后效性的例子。

3. 重复子问题：一个子问题可以被重复利用到多个父亲状态中。我们发现在下面这张图中，f[3][2]既可以用来更新f[4][2]，又可以用来更新f[4][3]。那么，因为我们把它存在数组里，所以只需要计算一次f[3][2]，就可以使用很多次。也就是说，f[4][2]和f[4][3]有个共同的子问题f[3][2]。

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。

选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

练习

最大子段和
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入描述：

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 a i a_i ai​。

输出描述：

输出一行一个整数表示答案。

示例 1：

输入：
7
2 -4 3 -1 2 -4 3
输出：
4

代码：

#include 
#define N 100000
using namespace std;

int n;
int a[N]; 
int b[N]; // 用于存储当前位置元素的最大字段和

int main() {
    // 输入
    cin >> n;
    for (int i = 0; i < n; ++i) 
        cin >> a[i];
    b[0] = a[0];

    // 动态规划过程
    for (int i = 1; i <= n; ++i)
        if (b[i - 1] < 0) {
            b[i] = a[i]; 
        } else { 
            b[i] = b[i-1] + a[i];
        }

    // 输出
    int ans = 0;
    for (int i = 0; i < n; ++i) 
        ans = max(ans, b[i]);    // 求第n行的最大值
    cout << ans << endl;

    return 0;
}

0-1背包问题 背包问题分析

给定n个物品，每个物体有个体积 v i v_i vi​和一个价值 p i p_i pi​。现有一个容量为V的背包，请问如何选择物品装入背包，使得获得的总价值最大？

基本思路

考虑到现在我们能做的决策，只有对于每个物品的“选”与“不选”。所以，这个问题就是:

• 以“将每一个物品依次放入背包”划分不同阶段
• 而对于每个物品的“选与不选”就是不同决策

考虑到所有的放置前i个物品的方案数可以分为两类：

• 一个是放第i个物品，
• 一个是不放第i个物品

所以下面我们分这两种情况来讨论。因为在决策的过程中，变化的是当前所在的阶段，以及容量的剩余大小。

所以，我们维护一个二维状态f[i, j], 来表示前i个物品，放到体积为j的背包里，可以得到的最大价值。

首先，考虑容量为任意值j时，将前i个物品放入背包的情况。

• 如果我们不选择第i个物品，那么总共j大小的背包空间相当于都用来放前(i - 1)的物品。那么我们如果想收益最大，就应该在前i-1个物品中选一个最优秀的子集。而解决”对于前i-1个物品，容量为j的背包，能获得的最大收益”就变成了一个子问题！
• 所以，当前的答案应该等于f[i - 1, j]。
• 另一种决策就是选择第i个物品。当我们一定选择第i个物品时，整个背包一定要分出v[i]的空间来放它。这样一来，一个容量为j的背包里，只剩下j - v[i]的空间来放前i - 1个物品了。而当前这个背包中所有物品的总收益，就是第i个物品的收益，加上用j-v[i]的空间装前i-1个物品的收益。我们发现，后者就是原问题的一个子问题！所以这种情况的最大收益是f[i - 1][j - v[i]] + p[i]。

然后，当我们讨论完到达当前状态的两种决策以及各自的收益，我们应该选择哪种决策呢？

当然是选择收益更大的那个！所以，我们有下面的式子：
f [ i , j ] = m a x { f [ i − 1 , j ] , f [ i − 1 , j − v [ i ] ] + p [ i ] } f[i,j]=max\{f[i−1,j],f[i−1,j−v[i]]+p[i]\} f[i,j]=max{f[i−1,j],f[i−1,j−v[i]]+p[i]}

背包问题的形式化分析

使用动态规划解决问题，需要明确状态设计、转移方程、初始状态和转移方向四个方面。

那现在，让我们来明确一下该背包问题中的动态规划四要素：

1. 状态：

   用f[i][j]表示前i个物品，放在空间为j的背包里，能获得的最大收益。

2. 转移方程：

   因为每一个阶段有至多两种选择，所以需要分别计算两种选择的收益后取较大值。

   f[i][j] = f[i - 1][j]							    		// j < v[i]，表示装不下第i个物品
   f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + p   [i]);	// otherwise
   

3. 初始状态：

   在一个物品都没放的时候，无论背包大小多少，总价值都是0，即

   f[0][j] = 0  // 0 <= j <= V
   

4. 转移方向：

   观察转移方程，发现要想保证等式右边的状态一定比左边的状态先算出来，只需要保证i从小到大计算即可。

最终该问题的答案就是f[n, V]。这样，背包问题就可以使用动态规划来解决。

代码实现

#include 
#define N 1002
using namespace std;

int n, V, v[N], p[N];
int f[N][N]; 

int main() {
    // 输入
    cin >> V >> n;		// V是总体积，n是物品总个数
    for (int i = 1; i <= n; ++i) 
        cin >> v[i] >> p[i];
    
    // 动态规划
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= V; ++j) {
            if (j < v[i]) 
                f[i][j] = f[i - 1][j];	// 当前背包容量不够装第i个物品	
            else 
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + p[i]); // otherwise
        }
    } 
	
    // 输出
    cout << f[n][V] << endl;
    return 0;
}

复杂度分析

1. 空间复杂度

因为最大用了二维数组，所以空间复杂度是O(nV)。

2. 时间复杂度

我们可以看出，整个算法用了两个for循环来实现，所以时间复杂度是O(nV)。

或者我们也可以用另一个思路来分析动态规划的时间复杂度：

因为一共有nV个状态，而每个状态只需要O(1)的时间计算转移方程，所以总时间复杂度是

总 时 间 复 杂 度 = 状 态 数 × 得 到 每 个 状 态 的 时 间 复 杂 度 = n V × O ( 1 ) = O ( n V ) 总时间复杂度 = 状态数\times得到每个状态的时间复杂度 = nV \times O(1) = O(nV) 总时间复杂度=状态数×得到每个状态的时间复杂度=nV×O(1)=O(nV)
可以看出这个算法和物品个数、背包容量都有关。

并且我们发现，这个算法可能不适用于背包容量非常大（例如10^9），每个物品的体积也非常大的情况。

滚动数组优化

整个动态规划的过程就是一个填表的过程，在本题中，填表的顺序就是：填完上一行，然后填下一行。而且我们发现，下一行的状态，只会用到上一行的状态来转移。所以，当我们在计算第i行时，其实前i-2行的状态就都没必要保留了。所以，我们可以用一种类似于”踩石头过河“的思想。

在空间优化的方法中，有一种很常见就是利用过河的思想。这种方法叫做滚动数组。在整个算法过程中，我们只用 2 × V 2\times V 2×V的数组f[2][V]来记录状态。其中，所有奇数行的状态填入f[1][j]中，所有偶数行的状态填入f[0][j]中，如下图:

所以整个代码实现就变成了

// ...
int f[2][N]; // 相当于只开了两个一维数组
int main() {
    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= V; ++j) {
        if (j < v[i]) 
            // i & 1是为了取i的奇偶性
            f[i & 1][j] = f[(i - 1) & 1][j];	
        else 
            f[i & 1][j] = max(f[(i - 1) & 1][j], f[(i - 1) & 1][j - v[i]] + p[i]);
        }
    } 
    
    // 输出
    cout << f[n & 1][V] << endl;
}

优化到一维数组

那么我们可不可以再进一步优化空间，使得只用一个一维数组就能解决整个问题了呢？

想到之前“踩石头过河”的类比，我们可能会觉得不太可能。但是如果我们进一步分析整个表的填写，如下图：

会发现下一行的某个状态，正好是由它上面的元素，以及左上方的某个元素转移而来。所以我们需要保证当计算黄色状态时上面两个绿色状态没有被覆盖掉。所以，当我们计算第i行时，完全可以将j从大到小枚举，这样在计算状态(i, j)之前，数组f[j]中存储的是状态f[i - 1, j]，更新完以后，f[j]中存的状态就是f[i, j]了。如下图：

所以代码可以这样写：

// ...
int f[N];	// 相当于只开了一个一维数组
int main() {
    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= v[i]; --j) {	
            // 只枚举到v[i]，是因为在v[i]之前，所有f[i][j] = f[i - 1][j]
            // 那么在一维数组的场景下，就相当于没有改变
            f[j] = max(f[j], f[j - v[i]] + p[i]);
        }
    } 
    
    // 输出
    cout << f[V] << endl;
}
// ...
int f[N];	// 相当于只开了一个一维数组
int main() {
    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= v[i]; --j) {	
            // 只枚举到v[i]，是因为在v[i]之前，所有f[i][j] = f[i - 1][j]
            // 那么在一维数组的场景下，就相当于没有改变
            f[j] = max(f[j], f[j - v[i]] + p[i]);
        }
    } 
    
    // 输出
    cout << f[V] << endl;
}