网站导航
> 文档中心 > 【算法基础】动态规划[二]——线性&区间dp(闫式dp分析法)

【算法基础】动态规划[二]——线性&区间dp(闫式dp分析法)

网友: 文档中心 2022-03-31 14:30:55

目录

  • 一、线性DP
    • 1、AcWing 898. 数字三角形
      • 算法 1
      • 算法2
    • 2、AcWing895. 最长上升子序列 [DP]
    • 3、AcWing 897. 最长公共子序列
    • 4、最短编辑距离
    • 5、编辑距离
  • 二、区间DP
    • AcWing 282. 石子合并
  • 三、总结

在这里插入图片描述

前言
欢迎关注我的专栏，想写完整个基础课的题解hh，开干🚀🚀🚀【算法基础】动态规划[二]——线性&区间dp(闫式dp分析法)

在这里插入图片描述

一、线性DP

1、AcWing 898. 数字三角形

题目链接
如果涉及到i-1的下标，一般考虑从1开始循环，保证数组不会越界。

算法 1

在这里插入图片描述
在这里插入图片描述

//思路一#include using namespace std;const int N = 510, INF = 1e9;int n;int f[N][N], a[N][N];int main ( ){    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 ++) { //需要多初始化俩个节点 0 开始到 i + 1 for (int j = 0; j <= i + 1;j ++) {     f[i][j] = -INF; //负无穷 }    }    f[1][1] = a[1][1];//起点    for (int i = 2; i <= n; i ++) {//涉及i-1 保证数组从1开始 for (int j = 1; j <= i; j++) {     f[i][j] = max(f[i - 1][j - 1], f[i - 1][j ]) + a[i][j]; }    } int res = -INF; //遍历每个尾结点    for (int i = 1; i <= n;i ++) { res = max(res, f[n][i]);    }    cout << res << endl;    return 0;}

算法2

在这里插入图片描述

//思路二#include using namespace std;const int N = 510;int n;int f[N][N];int main ( ){    cin >> n;    for (int i = 1; i <= n; i ++) { for (int j = 1; j <= i ; j ++){     cin >> f[i][j];//直接读入 相当于已经初始化了 }    }    for (int i = n - 1; i > 0; i--) { for (int j = 1  ; j <= i; j++) {     f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j]; }    }    cout << f[1][1] << endl;    return 0;}

2、AcWing895. 最长上升子序列 [DP]

补知识点

  • 子序列：可以不连续，但是相对位置得保持
  • 最长公共子序列(LCS）
    给出"ABCD" 和 “EDCA”，这个LCS是 “A” (或 D或C)，长度1
    给出 “ABCD” 和 “EACB”，这个LCS是"AC"长度2
  • 最长上升连续子序列（LICS）可以定义为从右到左或从左到右的序列。
    eg.给定 [5, 4, 2, 1, 3], 其最长上升连续子序列为 [5, 4, 2, 1], 长度 4.
    给定 [5, 1, 2, 3, 4], 其最长上升连续子序列为 [1, 2, 3, 4], 长度4.
  • 最长上升子序列：数值严格单调递增的子序列的长度最长
    在这里插入图片描述
#include using namespace std;const int N = 1010;int f[N];int a[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; //初始化 只有a[i]一个 for (int j = 1; j < i; j ++) {    if (a[i] > a[j]) {  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;}

3、AcWing 897. 最长公共子序列

题目链接
在这里插入图片描述

  • 如何 理解 01 和 10 ？？（上图）
    00的情况涵盖在01与10中,因此不考虑 f[i - 1 ][j - 1],最值不需要考虑重复，只需保证不漏即可。
  • 涉及到 i -1 所以a 下标从1开始
  • a+1表示什么？？
    +1表示a的地址往后移动1个字符位的地址 [指针]
  • 时间复杂度O(nm)
#include using namespace std;const int N = 1010;int f[N][N]; //开二维的 别问 问就是经验char a[N],b[N];int main(){     int n,m;    cin >> n >> m >> a + 1>> b + 1 ;//i - 1 问题 +1 防止数组越界    //防溢出；也可以使用"' '+str"     for (int i = 1; i <= n; i ++ ){ //遍历第一个字符串 for (int j = 1; j <= m; j ++ ){//遍历第二个字符串    f[i][j] = max (f[i - 1][j],f[i][j - 1]);    if (a[i] == b[j]){      f[i][j] = max (f[i][j],f[i - 1][j - 1] + 1);    } }    }    cout << f[n][m] << endl;  return 0;}

4、最短编辑距离

在这里插入图片描述

  • 集合 ： 所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合
  • 状态划分 以对a中的第i个字母操作不同划分
  • 添加 dp[i][j] = dp[i][j-1] + 1 (前a的前i个已经和b的前j-1个已经相同)
  • 删除 dp[i][j] = dp[i-1][j] + 1(a中前i-1已经和b的前j个已经相同)
  • 替换 dp[i][j] = dp[i-1][j-1] + 1(前i-1个已经相等，判断最后一个字母即可)

时间复杂度O(n2)

#include  using namespace std;const int N = 1010;int n,m;char a[N],b[N];int f[N][N];int main () {scanf("%d%s", &n, a+1);scanf("%d%s", &m, b+1);for(int i = 0; i <= n; i ++) f[i][0] = i;//初始化 a for(int j = 0; j <= m; j ++) f[0][j] = j;//初始化 bfor(int i = 1; i <= n; i ++) {for(int j = 1; j <= m; j ++) {f[i][j] = min(f[i - 1][j] ,f[i][j - 1]) + 1; //取删or增的最优解 if(a[i] == b[j]) {f[i][j] = min(f[i][j], f[i - 1][j - 1]);//一样则不操作 }else {f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); //增 } }} //cout << f[n][m] << endl;printf("%d\n", f[n][m]);return 0;}

5、编辑距离

题目链接

思路同上题一样

#include  using namespace std;const int N = 20,M = 1010;char str[M][N];int f[N][N];int fz(char a[],char b[]) {    int l1 =strlen(a + 1), l2 = strlen(b + 1);//注意 + 1  for (int i = 0; i <= l1; i ++ ) f[i][0] = i;     for (int j = 0; j <= l2; j ++ ) f[0][j] = j;   for (int i = 1; i <= l1; i ++ ){for (int j = 1; j <= l2; j ++ ) {  f[i][j] = min(f[i - 1][j] + 1,f[i][j - 1] + 1) ;  f[i][j] = min(f[i][j],f[i - 1][j - 1] + (a[i] != b[j])); }     }return f[l1][l2];}int main () {  int n,m;cin >> n >> m;for (int i = 0; i < n; i ++) {  cin >> (str[i] + 1); //注意}while (m --) {  char a[N];   int b;  cin >> (a + 1) >> b;//注意  int res = 0;  for(int i = 0; i < n ; i ++) {    if(fz(str[i],a) <= b) {      res ++;      }    }  cout << res << endl;}return 0;}

二、区间DP

AcWing 282. 石子合并

题目链接
石子合并
注意题目是每次只能合并相邻两堆, 与果子和并不同 [贪心]
前缀和：s[i] = s[i] + s[i - 1]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yZc2AnPG-1648443202826)(C:\Users\27285\AppData\Roaming\Typora\typora-user-images\image-20220325172339434.png)]

#include using namespace std;const int N = 310;int s[N];int f[N][N];//(树状)开二维 经验int main () {    int n;    cin >> n;    for (int i = 1; i <= n; i ++) { cin >> s[i]; s[i] += s[i - 1]; //前缀和    }    for (int len = 2; len <= n; len ++) { //枚举长度(小>>大) 长度应为2开始枚举 for (int l = 1; l + len - 1 <= n; l ++) {//枚举 左端点     int  r = l + len - 1;     f[l][r] = 1e8;//初始化为无穷大     for (int k = l; k < r;k ++) { //枚举决策  f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]+ s[r] - s[l - 1]) ;     } }    }    cout << f[1][n];    return 0;}

三、总结

  • DP状态计算的依据就是寻找最后一步不同点
  • 区间DP = DP + 前缀和

本文参考———y总的算法基础课

在这里插入图片描述

网络标签：

相关问题