算法板子：线性DP——算出三角形中的最大路径值、求最长上升子序列、求最长公共子序列

目录

 一、数字三角形——算出三角形中的最大路径值

二、最长上升子序列——求一个数组中的最长递增子序列

三、最长公共子序列——求两个字符串中的最长公共子序列

 一、数字三角形——算出三角形中的最大路径值

#include <iostream>
using namespace std;const int N = 500 + 10;
int a[N][N];int main()
{int n;cin >> n;// 存储三角形for (int i = 0; i < n; i ++ )for (int j = 0; j <= i; j ++ )cin >> a[i][j];// 从三角形的倒二行开始倒着遍历; 对于每一行的每一个元素，将该元素左下角和右下角中更大的元素加在其本身上; 比如倒二行的第一个元素，4和5中5更大，加在2上变成7.for (int i = n - 2; i >= 0; i -- )for (int j = 0; j <= i; j ++ )a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j];// 三角形中最大路径值存在(0,0)位置cout << a[0][0] << endl;return 0;
}

二、最长上升子序列——求一个数组中的最长递增子序列

#include <iostream>
using namespace std;const int N = 1000 + 10;// a数组存储题目中给定的数组
// f[i]代表以i指针所指元素结尾的上升子序列的长度; f[4]=3代表以下标4元素结尾的子序列的长度为3
int a[N], f[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ) cin >> a[i];// 初始化最长上升子序列的长度为1int ans = 1;// 初始化f数组元素全为1for (int i = 0; i < n; i ++ ) f[i] = 1;// 指针i从下标1开始遍历数组for (int i = 1; i < n; i ++ ){// 指针j从下标0遍历到指针i之前for (int j = 0; j < i; j ++ )// 如果发现j所指元素小于i所指元素，那么可以构成上升子序列，更新f[i]if (a[j] < a[i]) f[i] = max(f[j] + 1, f[i]);ans = max(ans, f[i]);}cout << ans << endl;return 0;
}

三、最长公共子序列——求两个字符串中的最长公共子序列

#include <iostream>
using namespace std;const int N = 1000 + 10;// f[i][j]中的指针i指向s1，指针j指向s2，f[i][j]代表s1中指针i之前的部分和s2中指针j之前的部分的最长公共子序列的长度; f[7][9]=3代表s1中的前7个字符和s2中的前9个字符的最长公共子序列的长度为3
int f[N][N];
int n, m;
string s1, s2;int main()
{cin >> n >> m >> s1 >> s2;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )// 如果s1的i-1位等于s2的j-1位，那么这一位可以并入s1的前i位和s2的前j位的公共子序列中，更新前i位和前j位的最长公共子序列的长度if (s1[i - 1] == s2[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;// 如果不相等，一个是i-1一个是j-1求maxelse f[i][j] = max(f[i - 1][j], f[i][j - 1]);cout << f[n][m] << endl;return 0;
}