本章面向大纲展开,以几个经典问题展开,伴随引导问题进行思考
真正认识动态规划,而不是仅仅背模板
经典问题包括: 数字三角形,LIS,LCS,石子合并
动态规划的基本思路【4】
在信息学竞赛中,第一次考查动态规划是在 IOI 1994(国际信息学竞赛)中的“数塔问题”,虽然当时全世界信息学顶尖选手的此题得分率极低,但是现在已经作为DP算法的入门题出现。其模型比较直观,有助于我们理解动态规划算法中的相关概念和性质。
很多老师在讲授动态规划时,先罗列相关非常生涩的概念,很多学生无法真正理解,下面我们从一个相对直观的问题出发,一步一步引导学生去主动思考,在解决问题的过程中,学生可以理解问题的本质。
问题:数塔问题(动态规划算法基本原理)
有一些数字排成数塔的形状,
其中第一层有一个数字,第二层有两个数字,……,第n层有n个数字。
现在要从第一层走到第n层,每次只能选择左下方或者右下方的数字,
问:“最后将路径上所有数字相加后得到的和最大是多少?”
引导思考:
(1)从起点到第一行第一列的答案是固定的。
(2)在第一步骤基础上,从起点到第二行的答案也是固定的。
(3)在第三行时,7 有两种选择,显然会选择累积更大的 8 过来才是最优的
若将f[i][j]定义为从第一行第一列到第 i 行第 j 列的路径上的数字和的最大值,
则到 数字7 的递推式为:f[3][2] = max(f[2][1],f[2][2]) + 7
(4)可得出一般递推式为 f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]
我们只需要推到第n行,就可以得到ans = max{f[n][1…n]}
解法提炼:
(1)状态定义:
f[i][j]定义从第一行第一列到第 i 行第 j 列的路径上的数字和的最大值
(2)所求:
max{f[n][1…n]}
(3)状态转移:
f[i][j]=max(f[i-1][j-1],f[i-1][j]) + a[i][j]
正确性分析:
(1)前面推导的结果不会随着后几行得到的结果而改变——无后效性。
(2)局部最优可以保证全局最优——最优子结构。
这两个性质也是动态规划算法解决问题的先决条件。
// 数字三角形示例代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int a[N][N], dp[N][N], n;
int main(){
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
// 填表法
memset(dp, -0x3f, sizeof dp);
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++){
dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i][j]);
if (j > 1) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i][j]);
}
int ret = -2e9;
for (int j = 1; j <= n; j++) ret = max(ret, dp[n][j]);
cout << ret << '\n';
return 0;
}
例题,【例9.2】数字金字塔
//数字三角形模型
简单一维动态规划【4】
问题:最长上升子序列问题(动态规划的状态定义)
给定一个长度为 n 的数字序列,求最长的上升子序列长度。
如3、1、2、6、4、5的最长上升子序列为1、2、4、5,故答案为4。
在数塔问题的基础上,很容易想到如下解法:
(1)状态定义:
f[i] 定义为到第 i 个数字为止,能获得最长子序列长度
(2)所求:
f[n]
(3)状态转移:
显然很难寻找到 f[i] 关于 f[1…i-1] 的递推关系。
无法找到递推关系是由于递推时的大小关系需要明确第 i 个数与前面某个确定的数进行比较,而原有的状态定义无法获得哪些数字被选中,故无法直接进行比较,带着这个问题,容易想到新的解法:
(1)状态定义:
f[i] 定义为到第 i 个数字为止,
且第 i 个数必须为该子序列的最后一个数字时,所获得的最长子序列的长度。
(2)所求:
max{f[1…n]}
(3)状态转移:
f[i] = max{f[j] + 1} | 1 <= j <= i-1, a[j] < a[i]。
该算法的时间复杂度为O(n^2),空间复杂度为O(n)。
// LIS示例代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], n;
int dp[N], ret;
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 填表法
a[0] = -2e9, dp[0] = 0;
for (int i = 1; i <= n; i++) // 枚举以i为结尾
for (int j = 0; j < i; j++) // 枚举从哪个数来
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
for (int i = 1; i <= n; i++) ret = max(ret, dp[i]);
cout << ret << '\n';
return 0;
}
例题,最长上升子序列
//LIS
问题:最长公共子序列问题
给定两个长度为 n 的数字序列,求最长的公共子序列长度。
第一个数字序列为 1、6、2、5、4、7,
第二个数字序列为 1、2、5、5、2、7,
则最长的公共子序列为1、2、5、7,其长度为4。
顺着LIS的思路,可以得到如下解法。
(1)状态定义:
f[i][j] 定义为当第一行数字取到第 i 个,第二行数字取到第 j 个时,
所能得到的最长公共子序列长度,
且第 i 个数字和第 j 个数字分别为所求子序列的最后一个数字(即这两个数字必须取到)
(2)所求:
max{f[1…n][1…n]}
(3)状态转移:
f[i][j] = 0 | a[i] ≠ b[j]
max(f[p][q]) + 1 | a[i] = b[j], a[p] = b[q]
该解法状态总数共有n^2个,
每个状态需要枚举i和j前面所有的p和q,求解单个状态需要的枚举量为(i-1)*(j-1),
其时间复杂度是O(n^2),
总共有n^2个状态,故总的时间复杂度为O(n^4),空间复杂度为O(n^2)。
该算法的瓶颈主要在于求解每个状态都需要去枚举前面所有的状态,
下面我们尝试使用另外一种状态定义。
(1)状态定义:
f[i][j] 定义为当第一行数字取到第 i 个,第二行数字取到第 j 个时,
所能得到的最长子序列长度,
且第 i 个数字和第 j 个数字不需要为所求子序列的最后一个数字(即这两个数字取到与否都可以)
(2)目标:
f[n][n]
(3)状态转移:
f[i][j] = f[i-1][j-1] + 1 | a[i] = b[j]
max(f[i-1][j], f[i][j-1]) | a[i] ≠ b[j]
当 a[i] 与 b[j] 相等时,其会对目标值贡献 +1,
而 a[i] 与 b[j] 不相等时,显然这两个数字无法配对,
故对 f[i][j] 而言,a[i] 和 b[j] 中必有一个是多余的,
故 f[i][j] = max(f[i-1][j], f[i][j-1])
此时计算f[i][j]的时间复杂度为O(1),故总的时间复杂度为O(n^2)。
例题,【例9.9】最长公共子序列
//LCS
问题:最大子段和问题
Given an array of n numbers, our task is to calculate the maximum subarray sum.
//举例
-1 2 4 -3 5 2 -5 2
//最大子段和是10
2 4 -3 5 2
Consider the subproblem of finding the maximum-sum subarray that ends at position k. There are two possibilities:
1. The subarray only contains the element at position k.
2. The subarray consists of a subarray that ends at position k − 1,
followed by the element at position k.
In the latter case, since we want to find a subarray with maximum sum, the subarray that ends at position k − 1 should also have the maximum sum. Thus, we can solve the problem efficiently by calculating the maximum subarray sum for each ending position from left to right.
int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
sum = max(array[k],sum+array[k]);
best = max(best,sum);
}
cout << best << "\n";
// 完整的示例代码 v1
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int maxn = -0x3f3f3f3f, area = 0;
for (int i = 1; i <= n; i++){
area += a[i];
if (area > maxn) maxn = area;
if (area < 0) area = 0; //另起炉灶
}
cout << maxn << '\n';
return 0;
}
// 完整的示例代码 v2
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int dp[20];
int maxn = -0x3f3f3f3f;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++){
dp[i] = max(dp[i - 1], 0) + a[i]; //另起炉灶
maxn = max(maxn, dp[i]);
}
cout << maxn << '\n';
return 0;
}
简单背包类型动态规划【5】
问题:01背包(Subset Sum)
有 n 件物品和一个容量是 m 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
(1)状态定义:
f[i][j] 定义为放到第i个物品为止,体积为j的最大价值
(2)目标:
f[n][m]
(3)状态转移:
f[i][j] = f[i - 1][j] , 不选第i个物品
f[i][j] = f[i - 1][j - v[i]] + w[i], 选第i个物品
例题,【例9.11】01背包问题
//01背包
例题,装箱问题
//任取若干个装入箱内,使箱子的剩余空间为最小
//01背包,输出V-dp[V]
问题:数塔问题加强版01
“加一维”思想在动态规划问题中的应用
在问题一的基础上,增加一个条件:
有且仅有一次机会可以将路径中的一个数字获得两次,求最后路径中路径上数字的和的最大值。
题目描述
有一些数字排成数塔的形状,其中第一层有一个数字,第二层有两个数字,……,第n层有n个数字。
现在要从第一层走到第n层,每次只能选择左下方或者右下方的数字,
有一张特权卡,只有一次使用机会,可以对当前数字取两次。
问:“最后将路径上所有数字相加后得到的和最大是多少?”
输入数据:
第一行,三个整数,n, x, y
后面每行为这个数字金字塔特定行包含的整数(数据保证输入的数都是非负数)
输入数据样例1:
3
1
1 2
1 1 1
输出数据样例1:
6
输入数据样例2:
3
1
1 8
14 8 8
输出数据样例2:
30
输入数据样例3:
3
1
1 10
11 10 10
输出数据样例3:
31
提示:
n <= 1e3, 0 <= a[i][j] <= 100
显然存在几种明显错误的贪心思想:
(1)在问题一基础上,对路径中最大的数字使用额外取一次的机会。
可构造如下反例:
1
1 8
14 8 8
经过问题一的处理,会发现路径为1-8-8,再对路径中最大值8额外取一次,最后结果为25,而显然存在更优的答案为1-1-14,其最后的结果为30。
(2)有了上述反例,又尝试进行如下的贪心策略:将所有数字中最大的数字选定,再以这个数字为起点往上取到顶,往下取到最后一行。又可构造反例如:
1
1 10
11 10 10
按照贪心策略,其路径为1-1-11,结果为24,而存在答案为1-10-10,31。
显然两种贪心策略刚好互为反例,无法兼顾,而如果在考场上仅仅为了获得更多的分数,可以采取将两种贪心策略分别计算,最后取两者中的最优值来进行骗分。
而正确做法就是本文要提出的“加一维”解法!
引导思考:
(1)在不使用额外机会时,与 数字三角形问题 是完全一样的。
(2)机会使用后,也与 数字三角形问题 是完全一样的。
(3)每个数字都有使用该机会的可能性。
提出解法:
(1)状态定义:
f[i][j][k] 定义为取到第 i 行第 j 列时,
机会的状态是 k 时能获得的目标值最优为多少,
k 为 0 表示机会已经使用,k 为 1 表示机会尚未使用。
(2)所求:
max(f[n][1..n][0])
(3)状态转移:
如果在第 i 行第 j 列时,机会依旧存在,则在此之前其机会也必须存在
故递推式为:
f[i][j][1] = max(f[i-1][j-1][1], f[i-1][j][1]) + a[i][j]
如果机会已经被使用,则f[i][j][0]有两种可能性:
在此之前机会已经被使用 max(f[i-1][j-1][0], f[i-1][j][0]) + a[i][j]
或者对a[i][j]使用取两次的机会max(f[i-1][j-1][1], f[i-1][j][1]) + 2 * a[i][j],
我们只需在这两种可能性中取最大值便可。
我们通过加入该机会是否被使用的状态作为新的一维,枚举其转移时的所有可能性,巧妙的解决了该问题,且时间复杂度和空间复杂度依旧和原问题同阶。
这种技巧也在大量的动态规划问题中适用,当我们无法很轻松的将“不可控的量”交代清楚时,可以将其状态作为单独的一维代入计算。
例题,【例9.21】方格取数
// 这道题目,也是一个加强版
// 走两遍
// 从左上走到右下,走了两次,问能取到的最大值
// 定义一个四维的状态,dp[N][N][N][N],
// 经过发现,可以优化到三维
问题:数塔问题加强版02
一种trick,挺巧妙
题目描述
有一些数字排成数塔的形状,其中第一层有一个数字,第二层有两个数字,……,第n层有n个数字。
现在要从第一层走到第n层,每次只能选择左下方或者右下方的数字,
经过的路径,必须经过指定的位置(x, y)
问:“最后将路径上所有数字相加后得到的和最大是多少?”
输入数据:
第一行,三个整数,n, x, y
后面每行为这个数字金字塔特定行包含的整数(保证输入的数据都是非负数)
输入数据样例:
3 2 1
1
1 2
1 1 1
输出数据样例:
3
提示:
n <= 1e3, 0 <= a[i][j] <= 100
问题:数塔问题加强版03
01 + 02 = 03
题面描述
有一些数字排成数塔的形状,其中第一层有一个数字,第二层有两个数字,……,第n层有n个数字。
现在要从第n层走到第1层,每次只能选择左上方方或者右上方的数字,
两个限制条件:
1、经过的路径,必须经过指定的位置(x, y)
2、有一张特权卡,只有一次使用机会,可以对当前数字取两次
问:“最后将路径上所有数字相加后得到的和最大是多少?”
输入数据:
第一行,三个整数,n, x, y
后面每行为这个数字金字塔特定行包含的整数(保证输入的数据可能是负数)
输出数据:
一个整数,经过(x, y)走到第一行,数字之和的最大值
输入数据样例:
5 3 2
7
3 -8
8 1 0
2 7 4 4
4 5 2 6 5
输出数据样例:
30
提示:
注意,数字三角形中的数据,可能都是负数
n <= 1e3, -1e7 <= a[i][j] <= 1e7
简单区间类型动态规划【5】
问题,石子合并
题目描述:
在一个操场上一排地摆放着N堆石子。
现要将石子有次序地合并成一堆。
规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。
计算出将N堆石子合并成一堆的最小得分。
若最初的第 l 堆石子和最初的 第 r 堆石子被合并成一堆,则说明 l~r 之间的每堆石子也已经被合并,
这样,l 和 r 才有可能相邻。
[l, r]表示这堆石子是由最初的第 l~r 堆石子合并而成的
则一定才在一个整数k,l <= k < r
在[l, r]这堆石子形成之前,先有的[l, r]被合并成一堆,[k+1, r]被合并成一堆,
然后,这两堆石子才能合并成[l, r]
对应到动态规划中,两个长度较小的区间上的信息向一个更长的区间发生了转移,
划分点 k 就是转移的决策。
自然地,应该把区间长度 len 作为DP的阶段。
因为区间长度可以由左端点和右端点表示出,即 len = r - l + 1
在设计状态的时候,本着“选择最小的能覆盖状态空间的维度集合”的思想,只用左、右端点表示DP的状态。
不是f[len][l][r], 而是f[l][r]
状态定义
f[l][r]表示把最初的第 l 堆到第 r 堆石子合并成一堆,需要消耗的最少体力
初始状态
f[i][i] = a[i]
状态转移方程
f[l, r] = min{f[l, k] + f[k + 1, r]} + sum of [l, r] | l <= k < r
目标
f[1][n]
在编程实现动态规划的状态转移方程时, 务必分清阶段、状态与决策,三者应按照从外到内的顺序依次循环
例题,【例9.18】合并石子
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int a[N], s[N], n;
int f[N][N]; // f[i][j]表示合并[i,j]区间的石子需要耗费的体力
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++) f[i][i] = 0; // 自己一个的时候,不用合并,耗费是0
for (int len = 2; len <= n; len++) // 阶段,有两个石子才发生合并的行为
for (int i = 1; i <= n - len + 1; i++){ // 状态 左端点i
int j = i + len - 1; // 状态 右端点j
for (int k = i; k < j; k++) // 决策
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
f[i][j] += s[j] - s[i - 1];
}
cout << f[1][n] << '\n';
return 0;
}
大纲要求
【4】动态规划的基本思路
【4】简单一维动态规划
【5】简单背包类型动态规划
【5】简单区间类型动态规划
例题代码
// LCS O(n^4)
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int n, m;
int f[N][N];
int main(){
scanf("%s", a + 1);
scanf("%s", b + 1);
n = strlen(a + 1), m = strlen(b + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) f[i][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
for (int p = 1; p < i; p++)
for (int q = 1; q < j; q++){
if (a[i] == b[j] && a[p] == b[q])
f[i][j] = max(f[i][j], f[p][q] + 1);
}
}
int ret = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ret = max(ret, f[i][j]);
cout << ret << '\n';
return 0;
}
// 数塔问题加强版01
// 有一个特权卡,可以在其中一个点取两次
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N][2]; // f[i][j][0]表示走到[i][j]使用了特权,f[i][j][1]表示走到了[i][j]还没使用特权
int a[N][N], n;
int main(){
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
f[1][1][0] = a[1][1] * 2, f[1][1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++){
f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][1]) + a[i][j];
f[i][j][0] = max(max(f[i-1][j][0], f[i-1][j][0]) + a[i][j], max(f[i-1][j-1][1], f[i-1][j][1]) + a[i][j]*2);
}
int ret = -0x3f3f3f3f;
for (int j = 1; j <= n; j++) ret = max(ret, f[n][j][0]);
cout << ret << '\n';
return 0;
}
// 数塔问题加强版02 数据都是正数,a[i][j] < 100
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, x, y;
int a[N][N], f[N][N];
int main(){
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
a[x][y] += 1e9; // 在(x,y)这个位置加上一个极大值,那么肯定会走这个点,必须的必
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];
int ret = 0;
for (int j = 1; j <= n; j++) ret = max(ret, f[n][j]);
cout << ret - 1e9 << '\n';
return 0;
}
// 数塔问题加强版03 第一个版本
// 有一个特权卡,可以在其中一个点取两次
// 从下往上递推
// [x,y]必须走
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
ll f[N][N][2]; // f[i][j][0]表示走到[i][j]使用了特权,f[i][j][1]表示走到了[i][j]还没使用特权
ll f2[N][N][2];
ll a[N][N];
int x, y, n;
int main(){
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
// 把x那行,非[x,y]的点,全都置成极小值,这样就不会走其他的点,从而肯定会走[x,y]
for (int j = 1; j <= x; j++) if (j != y) a[x][j] = -1e17;
for (int j = 1; j <= n; j++) f[n][j][0] = a[n][j] * 2, f[n][j][1] = a[n][j];
for (int i = n - 1; i >= 1; i--)
for (int j = 1; j <= i; j++){
f[i][j][1] = max(f[i+1][j][1], f[i+1][j+1][1]) + a[i][j];
f[i][j][0] = max(
max(f[i+1][j][0], f[i+1][j+1][0]) + a[i][j],
max(f[i+1][j][1], f[i+1][j+1][1]) + a[i][j]*2
);
}
ll ret = max(f[1][1][0], f[1][1][1]); // 数据当中有可能都是负数,不使用特权卡更好一点
cout << ret << '\n';
return 0;
}
/*
5 3 2
7
3 -8
8 1 0
2 7 4 4
4 5 2 6 5
30
*/
// 数塔问题加强版03 第二个版本
// 有一个特权卡,可以在其中一个点取两次
// 从下往上递推
// 必须经过[x,y]
// 分成两个部分,第一部分先从第n行爬到第x行,得到f[x][y][0] f[x][y][1]
// 第二部分,从x-1行往顶部继续爬,使用新的f2[][][]数组存储数据,f[x][y][0/1]作为现在的初始状态
// 从而保证必须进过[x,y]点,爬到[1,1]
// 另外,数据可能有炸,都是负数,最后可能不用特权卡更好一点
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
// f[i][j][0]表示走到[i][j]使用了特权,f[i][j][1]表示走到了[i][j]还没使用特权
ll f[N][N][2];
ll f2[N][N][2];
ll a[N][N];
int n, x, y;
int main(){
memset(f, 0xcf, sizeof f);
memset(f2, 0xcf, sizeof f2);
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
for (int j = 1; j <= n; j++) f[n][j][0] = a[n][j] * 2, f[n][j][1] = a[n][j];
for (int i = n - 1; i >= x; i--)
for (int j = 1; j <= i; j++){
f[i][j][1] = max(f[i+1][j][1], f[i+1][j+1][1]) + a[i][j];
f[i][j][0] = max(
max(f[i+1][j][0], f[i+1][j+1][0]) + a[i][j],
max(f[i+1][j][1], f[i+1][j+1][1]) + a[i][j]*2
);
}
f2[x][y][0] = f[x][y][0], f2[x][y][1] = f[x][y][1];
for (int i = x - 1; i >= 1; i--)
for (int j = min(i, y); j >= 1; j--){
f2[i][j][1] = max(f2[i+1][j][1], f2[i+1][j+1][1]) + a[i][j];
f2[i][j][0] = max(
max(f2[i+1][j][0], f2[i+1][j+1][0]) + a[i][j],
max(f2[i+1][j][1], f2[i+1][j+1][1]) + a[i][j]*2
);
}
cout << max(f2[1][1][0], f2[1][1][1]) << '\n';
return 0;
}
/*
5 3 2
7
3 -8
8 1 0
2 7 4 4
4 5 2 6 5
30
*/