NO.85十六届蓝桥杯备战|动态规划-经典线性DP|最长上升子序列|合唱队形|最长公共子序列|编辑距离(C++)

经典线性dp问题有两个：最⻓上升⼦序列（简称：LIS）以及最⻓公共⼦序列（简称：LCS），这两道题⽬的很多⽅⾯都是可以作为经验，运⽤到别的题⽬中。⽐如：解题思路，定义状态表⽰的⽅式，推到状态转移⽅程的技巧等等。
因此，这两道经典问题是⼀定需要掌握的

B3637 最长上升子序列 - 洛谷

1. 状态表⽰
   dp[i]表⽰：以i 位置元素为结尾的「所有⼦序列」中，最⻓递增⼦序列的⻓度。
   最终结果就是整张dp 表⾥⾯的最⼤值。
2. 状态转移⽅程：
   对于dp[i] ，我们可以根据「⼦序列的构成⽅式」，进⾏分类讨论：

• ⼦序列⻓度为1 ：只能⾃⼰玩了，此时dp[i] = 1 ；
• ⼦序列⻓度⼤于1 ：a[i]可以跟在前⾯某些数后⾯形成⼦序列。设前⾯的某⼀个数的下标为j，其中$1\le j<i$。只要a[j] < a[i]，i位置元素跟在j元素后⾯就可以形成递增序列，⻓度为dp[j]+1。
  因此，我们仅需找到满⾜要求的最⼤的dp[j] + 1即可。
  综上，dp[i] = max(dp[j] + 1, dp[i]) ，其中1 ≤ j < i && nums[j] < nums[i] 。

3. 初始化：
   不⽤单独初始化，每次填表的时候，先把这个位置的数改成1 即可。
4. 填表顺序：
   显⽽易⻅，填表顺序「从左往右」

#include <bits/stdc++.h>
using namespace std;const int N = 5010;int n;
int a[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int ret = 1;for (int i = 1; i <= n; i++){f[i] = 1;for (int j = 1; j < i; j++){if (a[j] < a[i]){f[i] = max(f[i], f[j] + 1);}}ret = max(ret, f[i]);}cout << ret << endl;return 0;
}

最长上升子序列2

利⽤贪⼼+⼆分优化动态规划：

• 我们在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
• 因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，最后⼀个元素是谁。为了尽可能的让这个序列更⻓，我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
• 统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];
int f[N], len;int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];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];}}cout << len << endl;return 0;
}

P1091 [NOIP 2004 提高组] 合唱队形 - 洛谷

对于每⼀个位置i ，计算：

• 从左往右看：以i 为结尾的最⻓上升⼦序列f[i] ；
• 从右往左看：以i 为结尾的最⻓上升⼦序列g[i] ；
  最终结果就是所有f[i] + g[i] - 1⾥⾯的最⼤值

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n;
int a[N];
int f[N], g[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];// 从左往右for(int i = 1; i <= n; i++){f[i] = 1;for(int j = 1; j < i; j++){if(a[j] < a[i]){f[i] = max(f[i], f[j] + 1);}}}// 从右往左for(int i = n; i >= 1; i--){g[i] = 1;for(int j = n; j > i; j--){if(a[j] < a[i]){g[i] = max(g[i], g[j] + 1);}}}int ret = 0;for(int i = 1; i <= n; i++){ret = max(ret, f[i] + g[i] - 1);}cout << n - ret << endl;return 0;
}

牛可乐和最长公共子序列

1. 状态表⽰：
   dp[i][j]表⽰：s1的[1,i]区间以及s2的[1,j]区间内的所有的⼦序列中，最⻓公共⼦序列的
   ⻓度。
   那么dp[n][m]就是我们要的结果。
2. 状态转移⽅程：
   对于dp[i][j] ，我们可以根据s1[i]与s2[j]的字符分情况讨论：
   a. 两个字符相同s1[i] = s2[j]：那么最⻓公共⼦序列就在s1的[1, i - 1]以及s2的[1, j - 1]区间上找到⼀个最⻓的，然后再加上s1[i]即可。因此dp[i][j] = dp[i - 1][j - 1] + 1；
   b. 两个字符不同s1[i] != s2[j]：那么最⻓公共⼦序列⼀定不会同时以s1[i]和s2[j]结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：

• 去s1 的[1, i - 1]以及s2的[1, j]区间内找：此时最⼤⻓度为dp[i - 1][j]；
• 去s1 的[1, i]以及s2 的[1, j - 1]区间内找：此时最⼤⻓度为dp[i][j - 1] ；
• 去s1 的[1, i - 1]以及s2 的[1, j - 1]区间内找：此时最⼤⻓度为dp[i - 1][j - 1]
  我们要三者的最⼤值即可。但是我们仔细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
  综上，状态转移⽅程为：
  if(s1[i] = s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
  if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。

3. 初始化：
   直接填表即可。
4. 填表顺序：
   根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右

#include <bits/stdc++.h>
using namespace std;const int N = 5010;string s, t;
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);while (cin >> s >> t){int n = s.size(), m = t.size();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][j], f[i][j-1]);}}cout << f[n][m] << endl;}return 0;
}

P2758 编辑距离 - 洛谷

两个字符串之间的dp 问题，与最⻓公共⼦序列的分析⽅式类似。

1. 状态表⽰：
   dp[i][j] 表⽰：字符串A 中[1, i] 区间与字符串B 中[1, j] 区间内的编辑距离。
   那么dp[n][m] 就是我们要的结果
2. 状态转移⽅程：
   对于dp[i][j] ，我们可以根据A[i] 与B[j] 的字符分情况讨论：
   a. 两个字符相同A[i] = B[j] ：那么dp[i][j]就是A的[1, i - 1]以及B的[1, j - 1]区间内编辑距离dp[i][j] = dp[i - 1][j - 1]，因此；
   b. 两个字符不同A[i] != B[j] ：那么对于A 字符串，我们可以进⾏下⾯三种操作：

• 删掉A[i]：此时dp[i][j]就是A的[1, i - 1]以及B的[1, j]区间内的编辑距离，因此dp[i][j] = dp[i - 1][j] + 1
• 插⼊⼀个字符：在字符串A的后⾯插⼊⼀个B[j]，此时的dp[i][j]就是A的[1, i]以及B的[1, j - 1]区间内的编辑距离，因此dp[i][j] = dp[i][j - 1] + 1；
• 将A[i]替换成B[j]：此时的dp[i][j]就是A的[1, i - 1]以及B的[1, j - 1]区间内的编辑距离，因此dp[i][j] = dp[i - 1][j - 1] + 1。
  我们要三者的最⼩值即可。

3. 初始化：
   需要注意，当i,j等于0的时候，这些状态也是有意义的。我们可以全部删除，或者全部插⼊让
   两者相同。
   因此需要初始化第⼀⾏dp[0][j] = j (1 ≤ j ≤ m) ，第⼀列dp[i][0] = i (1 ≤ i ≤ n) 。
4. 填表顺序：
   初始化完之后，从[1, 1] 位置开始从上往下每⼀⾏，每⼀⾏从左往右填表即可

#include <bits/stdc++.h>
using namespace std;const int N = 2010;string a, b;
int n, m;
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> a >> b;n = a.size(); m = b.size();a = " " + a; b = " " + b;//初始化for (int i = 1; i <= n; i++) f[i][0] = i;for (int j = 1; j <= m; j++) f[0][j] = j;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[i] == b[j]) f[i][j] = f[i-1][j-1];else f[i][j] = min(min(f[i-1][j], f[i-1][j-1]), f[i][j-1]) + 1;}}cout << f[n][m] << endl;return 0;
}