专业社交网站建设公司,wordpress模板小说,免费收录平台,西昌手机网站建设成都彩钢顶防水序列动态规划 一、意义二、例题1. 最长上升子序列2. 合唱队形#xff08;加强版#xff09;3. 公共子序列4. 编辑距离 一、意义
动态规划#xff08;dynamic programming#xff09;#xff0c;将一个目标大问题“大事化小#xff0c;小事化了”#xff0c;分成很多的子… 序列动态规划 一、意义二、例题1. 最长上升子序列2. 合唱队形加强版3. 公共子序列4. 编辑距离 一、意义
动态规划dynamic programming将一个目标大问题“大事化小小事化了”分成很多的子问题得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。
二、例题
1. 最长上升子序列
题目描述 对于给定的一个序列 a 1 , a 2 , ⋯ , a N a_1, a_2, \cdots, a_N a1,a2,⋯,aN我们也可以从中得到一些上升的子序列 a i 1 , a i 2 , ⋯ , a i K a_{i1}, a_{i2}, \cdots, a_{iK} ai1,ai2,⋯,aiK这里 1 ≤ i 1 i 2 … i K ≤ N 1 \le i1 i2 … iK \le N 1≤i1i2…iK≤N但必须按照从前到后的顺序。比如对于序列 1 , 7 , 3 , 5 , 9 , 4 , 8 1, 7, 3, 5, 9, 4, 8 1,7,3,5,9,4,8我们就会得到一些上升的子序列如 1 , 7 , 9 , 3 , 4 , 8 , 1 , 3 , 5 , 8 1, 7, 9, 3, 4, 8, 1, 3, 5, 8 1,7,9,3,4,8,1,3,5,8 等等而这些子序列中最长的如子序列 1 , 3 , 5 , 8 1, 3, 5, 8 1,3,5,8它的长度为 4 4 4因此该序列的最长上升子序列长度为 4 4 4。输入一个长度为 n n n 的序列输出该序列最长上升子序列长度。 输入描述 两行第一行包含一个整数 n n n第二行包含 n n n 个整数。 输出描述 一行一个整数表示该序列最长上升子序列长度。 样例1 输入 7
1 7 3 5 9 4 10输出 5提示 1 ≤ n ≤ 1000 1 \le n \le 1000 1≤n≤1000 先来推出状态转移方程以样例1为例
a[]17359410子序列11,71,31,3,51,3,5,91,3,41,3,5,9,10dp[]1223435
在上面的列举中dp[i] 表示的是以 a[i] 为子序列末尾的长度最大值。
而我们求出 dp[i] 的方法也有些麻烦
向前遍历 a[] 如果满足 a[i]a[k]当前遍历到的数字 a[i] 比之前遍历到的数字 a[k] 大打擂台求 dp[i] 的最大值
综合的时间复杂度大约是 O ( n 2 ) O(n^2) O(n2)感觉勉强能过。
综上所述我们写出如下代码
#include iostream
using namespace std;int n, maxn;
int a[1005];
int dp[1005];int main()
{cin n;for (int i 1; i n; i)cin a[i];for (int i 1; i n; i)for (int k i-1; k 1; k--)if (a[k] a[i]){dp[i] max(dp[i], dp[k]1);maxn max(maxn, dp[i]);}cout maxn1;return 0;
}2. 合唱队形加强版
题目描述 n n n 位同学站成一排音乐老师要请其中的 n − k n−k n−k 位同学出列使得剩下的 k k k 位同学排成合唱队形。 合唱队形是指这样的一种队形设k位同学从左到右依次编号为 1 , 2 , ⋯ , k 1,2,\cdots,k 1,2,⋯,k他们的身高分别为 t 1 , t 2 , ⋯ , t k t_1,t_2,\cdots,t_k t1,t2,⋯,tk则他们的身高满足 t 1 t 2 ⋯ t i − 1 t i t i 1 ⋯ t k − 1 t k t_1t_2\cdotst_{i-1}t_it_{i1}\cdotst_{k-1}t_k t1t2⋯ti−1titi1⋯tk−1tk。题目保证 1 ≤ i ≤ k 1≤i≤k 1≤i≤k。 你的任务是已知所有n位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。 输入描述 共二行。 第一行是一个整数 n n n表示同学的总数。 第二行有 n n n 个整数用空格分隔第 i i i 个整数 t i t_i ti 是第 i i i 位同学的身高 输出描述 一个整数最少需要几位同学出列
样例1 输入 8
186 186 150 200 160 130 197 220输出 4提示 0 n ≤ 1 0 5 , 1 ≤ t i ≤ 1 0 6 0n≤10^5,1≤t_i≤10^6 0n≤105,1≤ti≤106。 这道题目就是上一道题的加强版。这道题目会有两个 dp[] 数组
dp1[i]以 a[i] 为子序列结尾的最长上升子序列dp2[i]以 a[i] 为子序列结尾的最长下降子序列
那么就有如下代码
#include iostream
using namespace std;int n, maxn;
int a[100005];
int dp1[100005];
int dp2[100005];int main()
{cin n;for (int i 1; i n; i)cin a[i];for (int i 1; i n; i){dp1[i] 1;for (int j 1; j i; j)if (a[i] a[j])dp1[i] max(dp1[i], dp1[j]1);}for (int i n; i 1; i--){dp2[i] 1;for (int j n; j i; j--)if (a[i] a[j])dp2[i] max(dp2[i], dp2[j]1);}for (int i 1; i n; i)maxn max(maxn, dp1[i]dp2[i]-1);cout n-maxn;return 0;
}可是这样多半是超时。那么我们可以用一个数组 b[i] 来存储长度为 i 的情况下最后的一个值。这样对于第一题的 1 , 3 1,3 1,3 和 1 , 7 1,7 1,7 就会选择 1 , 3 1,3 1,3 了。即
a[]17359410子序列11,71,31,3,51,3,5,91,3,41,3,5,9,10dp[]1223435b[]11,71,31,3,51,3,5,91,3,4,91,3,4,9,10
所以第一题的代码可以优化为
#include iostream
#include algorithm
using namespace std;int n, maxn;
int len;
int a[1005];
int b[1005];
int dp[1005];int main()
{cin n;for (int i 1; i n; i)cin a[i];for (int i 1; i n; i){if (a[i] b[len]){len;b[len] a[i];dp[i] len;}else{int pos lower_bound(b1, blen1, a[i]) - b;b[pos] a[i];dp[i] pos;}}for (int i 1; i n; i)maxn max(maxn, dp[i]);cout maxn;return 0;
}作业1 恭喜题目 2 2 2 优化变成了你的作业不怀好意地笑。用 lower_bound() 函数进行优化。 3. 公共子序列
题目描述 现有一个数列 S S S如果分别是两个已知数列的子序列且是所有符合此条件序列中最长的则 S S S 称为已知序列的最长公共子序列。 举个例子如有两条随机序列如 1 3 4 5 5 1\ 3\ 4\ 5\ 5 1 3 4 5 5 和 2 4 5 7 5 6 2\ 4\ 5\ 7\ 5\ 6 2 4 5 7 5 6则它们的最长公共子序列便是 4 5 5 4\ 5\ 5 4 5 5。 现给定一个包含 n n n 个整数的整数序列和一个包含 m m m 个整数的整数序列输出这两个序列的最长公共子序列长度。 输入描述 输入包括三行第一行包含两个整数 n n n 和 m m m第二行包含 n n n 个整数第三行包含 m m m 个整数。 输出描述 输出包括一行一个整数表示这两个序列的最长公共子序列长度。 样例1 输入 5 6
1 3 4 5 5
2 4 5 7 5 6输出 3提示 1 ≤ n , m ≤ 1000 1\le n,m\le1000 1≤n,m≤1000。 按照题目的描述我们可以有一个 dp[][] 数组。其中 dp[i][j] 表示当 a 有 i i i 个数、b 有 j j j 个数的状态下最长的公共子序列长度。根据样例1则有以下存储
12345610000002000000301111140122225012333
所以得出式子
a[i] b[i] dp[i][j] dp[i-1][j-1] a[i] ! b[i] dp[i][j] max(dp[i-1][j], dp[i][j-1])
上代码
#include iostream
using namespace std;int n, m;
int a[1005];
int b[1005];
int dp[1005][1005];int main()
{cin n m;for (int i 1; i n; i)cin a[i];for (int i 1; i m; i)cin b[i];for (int i 1; i n; i)for (int j 1; j m; j){if (a[i] b[j])dp[i][j] dp[i-1][j-1]1;elsedp[i][j] max(dp[i-1][j], dp[i][j-1]);}cout dp[n][m];return 0;
}4. 编辑距离 设 A , B A,B A,B 是两个字符串。我们要用最少的字符操作次数将字符串 A A A 转换为字符串 B B B。这里所说的字符操作共有三种 删除一个字符插入一个字符将一个字符改为另一个字符。 #include iostream
#include string
#include algorithm
using namespace std;string a, b;
int dp[2005][2005];int main()
{cin a b;int lena a.length();int lenb b.length();a a;b b;for (int i 1; i lena; i)dp[i][0] i;for (int j 1; j lenb; j)dp[0][j] j;for (int i 1; i lena; i)for (int j 1; j lenb; j){if (a[i] b[j])dp[i][j] min({dp[i-1][j-1], dp[i-1][j]1, dp[i][j-1]1});elsedp[i][j] min({dp[i-1][j-1]1, dp[i-1][j]1, dp[i][j-1]1});}cout dp[lena][lenb];return 0;
}
