文章目录
前言
一、动态规划
二、例题，代码
AcWing 898. 数字三角形
本题解析
AC代码
AcWing 895. 最长上升子序列
本题解析
AC代码
AcWing 896. 最长上升子序列 II
本题解析
AC代码
AcWing 897. 最长公共子序列
本题解析
AC代码
AcWing 902. 最短编辑距离
本题解析
AC代码
AcWing 899. 编辑距离
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：动态规划——线性DP，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、动态规划
动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，个人认为是目前接触的所有算法里最绕的…
这里的题目的解题方法来自于：y总的闫氏dp分析法
二、例题，代码
AcWing 898. 数字三角形
本题链接：AcWing 898. 数字三角形
本博客提供本题截图：
本题解析
在这里我们规定一下行和列，行就是正常定义的行，列即图中的红色的线，即图中蓝色圈出来的位置为4行2列，用我们的数组表示的话就是f[4][2]
这里简单说一下，还是图中圈出来的那个数字7，得到它有两种路径，一种为从左上方8来，一种为从右上方1来，故状态计算为如图所示的形态，数组a表示的就是这个点上的值，如a[4][2] = 7
在这里还需要强调一下边界问题，因为涉及i - 1和j - 1故要数组下标从0开始，
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 510, INF = 1e9; int a[N][N], f[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) cin >> a[i][j]; for (int i = 0; i <= n; i ++ ) for (int j = 0; j <= i + 1; j ++ ) //对于从右上来的边界情况，需要赋值的时候为i + 1 f[i][j] = -INF; 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] + a[i][j], f[i - 1][j - 1] + a[i][j]); int res = -INF; for (int i = 1; i <= n; i ++ ) res = max (res, f[n][i]); cout << res << endl; return 0; }
AcWing 895. 最长上升子序列
本题链接：AcWing 895. 最长上升子序列
本博客提供本题截图：
本题解析
j指的是以i为结尾的上升子序列的倒数第二位数是哪一位 (编号)，j = 0代表之前没有比第i位小的数
这里需要注意，并不是所有的j都是满足题意的，必须要满足构成上升序列
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int a[N], f[N]; int main() { int n; 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); } int res = 0; for (int i = 1; i <= n; i ++ ) res = max (res, f[i]); cout << res << endl; return 0; }
