算法基础复盘笔记Day10【动态规划】—— 线性DP

第一章 线性dp

一、数字三角形

1. 题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 $i$ 行表示数字三角形第 $i$ 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

$1\le n\le 500$,
$-10000\le 三角形中的整数\le 10000$

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

---

2. 思路分析

状态表示：f[i][j] 表示从 $(1,1)$ 到 $(i,j)$ 的所有路径的集合。

状态计算：

• $(i,j)$ 这个点可以从 $(i-1,j)$ 走过来，即 f[i][j] = f[i - 1][j] + a[i][j]
• $(i,j)$ 这个点可以从 $(i-1,j-1)$ 走过来，即 f[i][j] = f[i - 1][j - 1] + a[i][j]
• 因此状态状态方程为：f[i][j] = max(f[i - 1][j] + a[i][j], f[i - 1][j - 1] + a[i][j])

最后，枚举最下面一层，返回最大的 f[n][i]即可。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int n  = 510, inf = 1e9;

int n;
int a[n][n];
int f[n][n]; //f[i][j]表示从(1,1)走到(i,j)的所有路径中，总和最大的那一条路径的总和

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 ++)
        for (int j = 0; j <= i + 1; j ++)
            f[i][j] = -inf; //初始化为负无穷
    
    f[1][1] = a[1][1]; //由f[i][j]的定义，(1,1)点的f值就是本身
    for (int i = 2; i <= n; i ++) //这样，我们从第二层枚举至第n层
        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]); //最大值在第n层的某一个点处取得
    
    cout << res << endl;
    
    return 0;
}

---

二、最长上升子序列

1. 题目描述

给定一个长度为 n 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

$1\le n\le 1000$，
$-10^9\le 数列中的数\le 10^9$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

---

2. 思路分析

状态表示：f[i] 表示 以 a[i] 为结尾 的最长上升子序列的长度。

初始条件：f[i] = 1

状态转移方程：$i$从第一个数开始枚举，1$\le$ $j$ $<$ $i$，如果 a[j] < a[i]，则 f[i] = max(f[i], f[j] + 1)

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int n = 1010;

int n;
int a[n], f[n];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];;
    
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1; //初始化，设f[i]默认为1，找不到前面数字小于自己的时候就为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;
}

---

三、最长上升子序列 ii

1. 题目描述

给定一个长度为 n 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

$1\le n\le 100000$，
$-10^9\le 数列中的数\le 10^9$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

---

2. 思路分析

最长上升子序列这道题的时间复杂度是 $o(n^2)$，用在这道题会超时。

如果把内层循环改为 二分查找，就能把内存查找时间降为 $logn$，则时间复杂度为 $o(nlogn)$。
但是，二分查找的前提是有序序列，故增加一个 $b$ 数组，用来记录上升子序列。
关键问题：动态更新 $b$ 数组。

考虑新进来一个元素 $a[i]$：

• 大则添加：如果 a[i] > b[len]，直接让 b[++ len] = a[i]。即 $b$ 数组的长度增加1，并且添加了一个元素；
• 小则替换：如果 a[i] <= b[len]，就用 a[i] 替换 $b$数组中第一个大于或等于 a[i] 的元素。假设第一个大于等于 a[i] 的元素是b[j]，那么用 a[i] 换掉 b[j] ，会使得 b[1....j] 这个上升子序列的结尾元素更小。对于一个上升子序列，其结尾元素越小，越有利于接上其他元素，也就越可能变得更长。

模拟过程：

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int n = 1e5 + 10;

int n;
int a[n], b[n]; //b数组记录上升子序列
int len; //上升子序列的长度

//二分查找第一个大于等于x的位置
int find(int x)
{
    int l = 1, r = len;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (b[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    
    b[++ len] = a[1];
    //动态更新b数组
    for (int i = 2; i <= n; i ++)
        if (a[i] > b[len])  //大于则添加
        {
            b[++ len] = a[i];
        }
        else //小于等于则替换
        {
            int tmp = find(a[i]); 
            b[tmp] = a[i];
        }
    
    cout << len << endl;
    
    return 0;
}

---

四、最长公共子序列

1. 题目描述

给定两个长度分别为 n 和 m 的字符串 a 和 b，求既是 a 的子序列又是 b 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 n 和 m。

第二行包含一个长度为 n 的字符串，表示字符串 a。

第三行包含一个长度为 m 的字符串，表示字符串 b。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

$1\le n,m\le 10001\le$

输入样例：

4 5
acbd
abedc

输出样例：

3

---

2. 思路分析

状态表示：f[i][j] 记录序列 a[1...i] 和 b[1...j]的最长公共序列长度。

考虑末尾元素 a[i] 与 b[j]是否在公共子序列中：

• 若 $a[i]=b[j]$，则 $a[i]$ 与 $b[j]$在公共子序列中，即 f[i][j] = f[i - 1][j - 1] + 1
• 若 $a[i]\ne b[j]$，且 $a[i]$不在公共子序列中，则可去掉 $a[i]$，即 f[i][j] = f[i - 1][j]
• 若 $a[i]\ne b[j]$，且 $b[j]$不在公共子序列中，则可去掉 $b[j]$，即 f[i][j] = f[1][j - 1]

状态转移方程：

• f[i][j] = f[i - 1][j - 1] + 1，$a[i]=b[j]$
• f[i][j] = max(f[i - 1][j], f[i][j - 1])，$a[i]\ne b[j]$

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int n = 1010;

int n, m;
char a[n], b[n];
int f[n][n];

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1; //下标从1开始
    
    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;
}

---

五、最短编辑距离

1. 题目描述

给定两个字符串 a 和 b，现在要将 a 经过若干操作变为 b，可进行的操作有：

1. 删除–将字符串 a 中的某个字符删除。
2. 插入–在字符串 a 的某个位置插入某个字符。
3. 替换–将字符串 a 中的某个字符替换为另一个字符。

现在请你求出，将 a 变为 b 至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 a 的长度。

第二行包含一个长度为 n 的字符串 a。

第三行包含整数 m，表示字符串 b 的长度。

第四行包含一个长度为 m 的字符串 b。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

$1\le n,m\le 1000$

输入样例：

10 
agtctgacgc
11 
agtaagtaggc

输出样例：

4

---

2. 思路分析

状态表示： f[i][j] 表示从 a[1...i] 到 b[1...j]的编辑距离。

• 若 $a[i]=b[j]$，即 f[i][j] = f[i - 1][j - 1]

• 若 $a[i]\ne b[j]$，则需要考察修改、插入和删除的编辑距离的最小值：

  • 修改操作：a[1...i-1] == b[1...j-1]，把 $a[i]$ 改为 $b[j]$，即 f[i][j] = f[i - 1][j - 1] + 1
  • 插入操作：a[1...i] == b[1...j-1]，在 $a[i]$ 后插入 $b[j]$，即 f[i][j] = f[i][j - 1] + 1
  • 删除操作：a[1...i - 1] == b[1...j]，删除 $a[i]$，即 f[i][j] = f[i - 1][j] + 1

状态转移方程：

• f[i][j] = f[i - 1][j - 1]，$a[i]=b[j]$
• f[i][j] = min(f[i - 1][j - 1],f[i - 1][j], f[i][j - 1]) + 1，$a[i]\ne b[j]$

---

3. 代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int n = 1010;

int n, m;
char a[n], b[n];
int f[n][n]; //把a[1~i]变成b[1~j]需要的步数

int main()
{
    cin >> n >> a + 1;
    cin >> m >> b + 1;
    
    //初始化
    for (int i = 0; i <= n; i ++ ) f[i][0] = i; //把a[1~i]变成b[0]需要i步
    for (int i = 0; i <= m; i ++ ) f[0][i] = i; //把a[0]变成b[1~i]需要i步
    
    //因为初始了边界情况，因此直接从1开始
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if(a[i] == b[j]) 
                f[i][j] = f[i - 1][j - 1];
            else
                f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i - 1][j] + 1 , f[i][j - 1] + 1));
        }

    printf("%d\n", f[n][m]);

    return 0;
}

---

六、编辑距离

1. 题目描述

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含一个字符串，表示给定的字符串。

再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10。

输出格式

输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

$1\le n,m\le 1000$

输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

---

2. 思路分析

状态表示： f[i][j] 表示从 a[1...i] 到 b[1...j]的编辑距离。

• 若 $a[i]=b[j]$，即 f[i][j] = f[i - 1][j - 1]

• 若 $a[i]\ne b[j]$，则需要考察修改、插入和删除的编辑距离的最小值：

  • 修改操作：a[1...i-1] == b[1...j-1]，把 $a[i]$ 改为 $b[j]$，即 f[i][j] = f[i - 1][j - 1] + 1
  • 插入操作：a[1...i] == b[1...j-1]，在 $a[i]$ 后插入 $b[j]$，即 f[i][j] = f[i][j - 1] + 1
  • 删除操作：a[1...i - 1] == b[1...j]，删除 $a[i]$，即 f[i][j] = f[i - 1][j] + 1

状态转移方程：

• f[i][j] = f[i - 1][j - 1]，$a[i]=b[j]$
• f[i][j] = min(f[i - 1][j - 1],f[i - 1][j], f[i][j - 1]) + 1，$a[i]\ne b[j]$

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int n = 15, m = 1010;

int n, m;
int f[n][n];
char str[m][n]; //存储给定的n个字符串

//字符串a变为字符串b的最短编辑距离
int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);
    
    //初始化
    for (int i = 0; i <= lb; i ++) f[0][i] = i;
    for (int i = 0; i <= la; i ++) f[i][0] = i;
    
    for (int i = 1; i <= la; i ++)
        for (int j = 1; j <= lb; 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[la][lb];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> (str[i] + 1);
    
    while (m --)
    {
        char s[n]; //存储给定查询的字符串
        int limit;
        cin >> (s + 1) >> limit;
        
        int res = 0;
        for (int i = 0; i < n; i ++) //每次枚举所有给定的字符串
            if (edit_distance(str[i], s) <= limit)
                res ++;
        
        cout << res << endl;
    }
    return 0;
}

---

创作不易，如果有帮助到你，请给文章点个赞和收藏，让更多的人看到！！！
关注博主不迷路，内容持续更新中。