美丽乡村建设发展论坛网站,网站年费如何做会计分录,营销平台推广,上海专业网络推广公司Acwing-基础算法课笔记之动态规划#xff08;线性DP#xff09; 一、数字三角形1、概述2、闫氏dp分析法代码示例 二、最长上升子序列1、概述2、闫氏dp分析法3、过程模拟4、代码演示 三、最长上升子序列强化版1、概述2、代码示例 四、最长公共子序列#xff08;LCS#xff0… Acwing-基础算法课笔记之动态规划线性DP 一、数字三角形1、概述2、闫氏dp分析法代码示例 二、最长上升子序列1、概述2、闫氏dp分析法3、过程模拟4、代码演示 三、最长上升子序列强化版1、概述2、代码示例 四、最长公共子序列LCS1、定义1分解2子问题 2、过程模拟3、代码示例 五、最短编辑距离1、定义1分解2子问题 2、过程模拟3、代码示例 一、数字三角形
1、概述
给定一个如下图所示的数字三角形从顶部出发在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点一直走到底层要求找出一条路径使路径上的数字的和最大。
2、闫氏dp分析法 代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 510;
int n;
int dp[N][N], w[N][N];
int main() {scanf(%d, n);for (int i 1; i n; i) {for (int j 1; j i; j) {scanf(%d, w[i][j]);}}for (int i 1; i n; i)dp[n][i] w[n][i];//因为从底部开始往上寻找所以将底部的dp先初始化for (int i n - 1; i 1; i--) {for (int j 1; j i; j) {dp[i][j] max(dp[i 1][j] w[i][j], dp[i 1][j 1] w[i][j]);}}printf(%d, dp[1][1]);return 0;
}二、最长上升子序列
1、概述
给定一个长度为N的数列A求数量单调递增的子序列的长度最长是多少。A的任意子序列B可表示为 B { A k 1 , A k 2 , . . . , A k p } B\{A_{k_1},A_{k_2},...,A_{k_p}\} B{Ak1,Ak2,...,Akp}其中 k 1 k 2 ⋯ k p k_1k_2\cdotsk_p k1k2⋯kp。
2、闫氏dp分析法 3、过程模拟
如何理解所有以第i个数结尾的上升子序列 例如 以 8 8 8为第 i i i个数则 8 8 8前面的上升子序列为 3 , 8 3,8 3,8 1 , 8 1,8 1,8 2 , 8 2,8 2,8 1 , 2 , 8 1,2,8 1,2,8
4、代码演示
#includeiostream
#includealgorithm
using namespace std;
const int N 1010;
int n;
int a[N], dp[N];
int main() {scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);}for (int i 1; i n; i) {dp[i] 1;for (int j 1; j i; j) {if (a[j] a[i]) {dp[i] max(dp[i], dp[j] 1);}}}int ans 0;for (int i 1; i n; i) {ans max(ans, dp[i]);}printf(%d, ans);return 0;
}三、最长上升子序列强化版
1、概述
由于数据范围比较大所以只能利用二分的思想先筛选出序列中最大的数找出该数前的最大上升子序列。
2、代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
int n;
int a[N], dp[N];
int main() {scanf(%d, n);for (int i 0; i n; i)scanf(%d, a[i]);int len 0;dp[0] -2e9;for (int i 0; i n; i) {int l 0, r len;while (l r) {int mid l r 1 1;if (dp[mid] a[i])l mid;else r mid - 1;}len max(len, r 1);dp[r 1] a[i];}printf(%d, len);return 0;
}四、最长公共子序列LCS
1、定义
例如 s 1 : A B C B D A B s_1:ABCBDAB s1:ABCBDAB s 2 : B D C A B C s_2:BDCABC s2:BDCABC D [ i ] [ j ] s 1 D[i][j]s_1 D[i][j]s1前 i i i个字符与 s 2 s_2 s2前 j j j个字符的 L C S LCS LCS 例如 D [ 7 ] [ 6 ] 4 D[7][6]4 D[7][6]4
1分解 1、 D [ i ] [ j ] D [ i − 1 ] [ j − 1 ] 1 D[i][j]D[i-1][j-1]1 D[i][j]D[i−1][j−1]1 2、 D [ i ] [ j ] m a x ( D [ i − 1 ] [ j ] D [ i ] [ j − 1 ] ) D[i][j]max\begin{pmatrix} D[i-1][j] \\ D[i][j-1] \end{pmatrix} D[i][j]max(D[i−1][j]D[i][j−1]) 2子问题 D 00 0 , D i 0 0 , D 0 j 0 D_{00}0,D_{i0}0,D_{0j}0 D000,Di00,D0j0
2、过程模拟 ⋇ \divideontimes ⋇如果两个字符串的末尾字符相同分析如下 ∙ \bullet ∙ D [ i ] [ j ] D [ i − 1 ] [ j − 1 ] 1 D[i][j]D[i-1][j-1]1 D[i][j]D[i−1][j−1]1 ⋇ \divideontimes ⋇如果两个字符串的末尾字符不同需要舍弃两字符串中的其中一个末尾的字符 x x x 或 y y y分析如下 ∙ \bullet ∙如果舍弃 s 1 s_1 s1 的 x x x则 D [ i ] [ j ] m a x ( D [ i − 1 ] [ j ] ) D[i][j]max(D[i-1][j]) D[i][j]max(D[i−1][j]) ∙ \bullet ∙如果舍弃 s 2 s_2 s2 的 y y y则 D [ i ] [ j ] m a x ( D [ i ] [ j − 1 ] ) D[i][j]max(D[i][j-1]) D[i][j]max(D[i][j−1])
画表格来描述 1、 D [ i ] [ j ] D [ i − 1 ] [ j − 1 ] 1 , s 1 [ i − 1 ] s 2 [ j − 1 ] D[i][j]D[i-1][j-1]1,s_1[i-1]s_2[j-1] D[i][j]D[i−1][j−1]1,s1[i−1]s2[j−1] 2、 D [ i ] [ j ] m a x ( D [ i − 1 ] [ j ] D [ i ] [ j − 1 ] ) , s 1 [ i − 1 ] ! s 2 [ j − 1 ] D[i][j]max\begin{pmatrix} D[i-1][j] \\ D[i][j-1] \end{pmatrix},s_1[i-1]!s_2[j-1] D[i][j]max(D[i−1][j]D[i][j−1]),s1[i−1]!s2[j−1] ∅ \varnothing ∅BDCABC ∅ \varnothing ∅0000000A0B0C0B0D0A0B0 ⇓ \Darr ⇓ ∅ \varnothing ∅BDCABC ∅ \varnothing ∅0000000A0000111B0111122C0112223B0112233D0122233A0122333B0122344
方法 看坐标 ( i , j ) (i,j) (i,j)的元素是否相等如果相等则以左斜上方的数为基础加 1 1 1否则等于左边的数。
如果不理解可以看一看这位大佬的视频
3、代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 1010;
int n, m;
int dp[N][N];
char a[N], b[N];
int main() {cin n m;cin a 1;cin b 1;for (int i 1; i n; i) {for (int j 1; j m; j) {if (a[i] b[j])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] 1);else dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}cout dp[n][m];return 0;
}五、最短编辑距离
1、定义 D [ i ] [ j ] D[i][j] D[i][j]等于 s 1 s_1 s1前 i i i个字符编辑为 s 2 s_2 s2的前 j j j个字符它的编辑距离。 例如 s u n sun sun编辑为 s a t u r satur satur则 D 35 3 D_{35}3 D353。
1分解 ⋇ \divideontimes ⋇如果 s 1 s_1 s1和 s 2 s_2 s2的末尾字符相同则只要编辑 s i − 1 s_{i-1} si−1的字符串变成 s j − 1 s_{j-1} sj−1的字符串的次数 ∙ \bullet ∙如果 s i − 1 s_{i-1} si−1等于 s j − 1 s_{j-1} sj−1则 D [ i ] [ j ] D [ i − 1 ] [ j − 1 ] D[i][j]D[i-1][j-1] D[i][j]D[i−1][j−1] ⋇ \divideontimes ⋇如果 s 1 s_1 s1和 s 2 s_2 s2的末尾字符不相同 ∙ \bullet ∙如果 s 1 s_1 s1的字符串末尾与 s 2 s_2 s2相比少了一个 y y y则在 s 1 s_1 s1的末尾插入 y y y则状态转移方程为 D [ i ] [ j ] D [ i ] [ j − 1 ] 1 D[i][j]D[i][j-1]1 D[i][j]D[i][j−1]1 ∙ \bullet ∙如果 s 1 s_1 s1的字符串末尾与 s 2 s_2 s2相比多了一个 x x x则删除 s 1 s_1 s1末尾的 x x x则状态转移方程为 D [ i ] [ j ] D [ i − 1 ] [ j ] 1 D[i][j]D[i-1][j]1 D[i][j]D[i−1][j]1 ∙ \bullet ∙如果 s 1 s_1 s1与 s 2 s_2 s2具有高度的相似性则将 s 1 s_1 s1当中的某个字符替换成 s 2 s_2 s2当中的某个字符则状态转移方程为 D [ i ] [ j ] D [ i − 1 ] [ j − 1 ] 1 D[i][j]D[i-1][j-1]1 D[i][j]D[i−1][j−1]1
在这三种条件中选最小
2子问题 D 00 0 , D i 0 i , D 0 j j D_{00}0,D_{i0}i,D_{0j}j D000,Di0i,D0jj
2、过程模拟 ∅ \varnothing ∅satur ∅ \varnothing ∅012345s1u2n3 ⇓ \Darr ⇓ ∅ \varnothing ∅satur ∅ \varnothing ∅012345s101234u211223n322233
方法 如果所在同一坐标的两个字符相等则该坐标的值等于左上方坐标的值。如果不相等则需要考虑是插入、删除还是替换。如果是插入则当前坐标的值等于左边坐标的值加 1 1 1。如果是删除则当前坐标的值等于上方的值加 1 1 1。如果是替换则当前坐标的值等于左上方的值加 1 1 1。
3、代码示例
#includeiostream
#includealgorithm
using namespace std;
const int N 1010;
int n, m;
char a[N], b[N];
int dp[N][N];
int main() {scanf(%d%s, n, a 1);scanf(%d%s, m, b 1);for (int i 1; i n; i)dp[i][0] i;for (int j 1; j m; j)dp[0][j] j;for (int i 1; i n; i) {for (int j 1; j m; j) {dp[i][j] min(dp[i][j - 1] 1, dp[i - 1][j] 1);if (a[i] b[j])dp[i][j] min(dp[i][j], dp[i - 1][j - 1]);else dp[i][j] min(dp[i - 1][j - 1] 1, dp[i][j]);}}printf(%d\n, dp[n][m]);return 0;
}
