开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划-线性DP -> 正文阅读

[数据结构与算法]动态规划-线性DP

前言

线性DP，顾名思义就是在线性空间上进行递推

以下是一些典型的例题

一、数字三角形

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

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

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

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

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

数据范围
1≤n≤500,
?10000≤三角形中的整数≤10000
输入样例：

输出样例：

思路：
题目要求出从顶部走到底部的路径上的最大数字和

我们用逆向思维来思考，必然存在一条路径是从底部到顶部且数字和最大，那么我们就采用从下至上的方式递推

我们用f[i][j]表示当前路径的最大数字和，i表示当前数字所在行，j表示当前数字所在列。而当前状态只能从f[i+1][j]和f[i+1][j+1]这两个状态转移过来，我们取其最大值再加上当前数字即可,f[0][0]即为从底部到顶部路径上的最大数字和。

由此得到的转移方程便是f[i][j] = max(f[i+1][j],f[i+1][j+1]) + f[i][j]

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int N = 510, M = 2010, mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
int n, m;
int f[N][N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
            scanf("%d", &f[i][j]);
    }
    for (int i = n - 2; i >= 0; i -- )
    {
        for (int j = 0; j <= i; j ++ )
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
    }
    printf("%d", f[0][0]);
    return 0;
}

二、最长上升子序列

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

输入格式
第一行包含整数 N。

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

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

数据范围
1≤N≤1000，
?109≤数列中的数≤109
输入样例：

7
3 1 2 1 8 5 6

输出样例：

思路：
在这里插入图片描述

我们定义f[i]为所有以第i个数结尾的上升子序列的最大长度，那么以上一个数结尾的就存在i-1类情况，要么是没有，要么是第一个数，要么是第j个数…要么就是第i-1个数，所以我们对每一类情况+1取max便可以得到当前状态的结果。

由此我们就可以得到状态转移方程，当a[j] < a[i] 的时候，f[i] = max(f[i],f[j] + 1)。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 1010, mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);

int a[N], f[N];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", a + i);
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
        {
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i ++ )
        ans = max(ans, f[i]);
    printf("%d", ans);
    return 0;
}

优化版的最长上升子序列

上面那个是朴素版的做法，时间复杂度为O(n²)，在数据范围小的情况下可以满足，但数据范围超1e5就要TLE了。

在这里插入图片描述

如果存在以数字3结尾的一个上升子序列，以1结尾的一个上升子序列，且3在1的前面。我们不难发现，如果当前数字可以接在3的后面，那么必然可以接在1的后面，那么我们就没有必要去保存以3结尾的上升子序列了。

假设我们求到第i个数的上升子序列，那么前面所有的上升子序列我们可以按长度分类，每个长度只存最小的一个数结尾。

我们可以将这个最小的数的值存到一个数组里面去，从而得到一个严格单调递增的数组。

我们每次只需要从这个数组种找到最大的一个小于a[i]的数，然后在这个数的后边接上a[i]即可。这一步我们可以用二分来做。

这样我们就可以得到一个O(n*lgn)的时间复杂度。

这种优化方式用到了贪心的思想。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 1e5 + 7, mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);

int a[N], q[N];
//q数组保存单调递增序列
int main()
{
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", a + i);
    int len = 0;
    //为了保证严格单调递增，设置边界小于任何元素
    q[0] = -2e9;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        //从q数组中找到小于a[i]的最大元素的下标，那么以a[i]结尾的最大长度就是r+1
        len = max(len, r + 1);
       //更新区间元素元素，留下更小的元素作为结尾
        q[r + 1] = a[i];
    }
    printf("%d", len);
    return 0;
}

三、最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数 N 和 M。

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

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

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

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

数据范围
1≤N,M≤1000
输入样例：

4 5
acbd
abedc

输出样例：

思路：
在这里插入图片描述
定义f[i][j]表示的是所有A[1~i]与B[1 ~ j]的公共子序列的最大长度

我们以最后一个字符是否包含可以划分为四种子状态

不包含a[i]b[j]，图中用00表示，f[i][j] = f[i-1][j-1]
不包含a[i]包含b[j]，图中用01来表示，f[i][j] = f[i-1][j]
包含a[i]不包含b[j]，图中用10来表示，f[i][j] = f[i][j-1]
包含a[i]b[j]，图中用11来表示，f[i][j] = f[i-1][j-1] + 1

我们仔细观察可以发现状态f[i][j]并没有规定一定要选a[i]b[j]，所以对于01和10这两种状态，它就包含了选与不选两种情况，所以这四种状态会出现重复情况，而且01和10这这两种情况一定包含00这种情况的。但是重复并不影响我们只求得最大值。

由此我们只需要考虑01、10和11这三种情况即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 1010, mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);

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

int main()
{
    scanf("%d%d%s%s", &n, &m, a + 1, b + 1);
    for (int i = 1; a[i]; i ++ )
    {
        for (int j = 1; b[j]; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            //当a[i] == b[j]时才满足11这种情况
            if (a[i] == b[j])
            {
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

四、最短编辑距离

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

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。

输入格式
第一行包含整数 n，表示字符串 A 的长度。

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

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

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

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

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

数据范围
1≤n,m≤1000
输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

思路：

在这里插入图片描述
我们用f[i][j]来表示当前状态，即将A序列前1 ~ i个字母转变成B序列前1 ~ j个字母的所有操作的最小操作次数

对于当前状态的第i个字符我们有三种操作

删除第i个字符使之与前j个字符匹配，这个操作我们就要考虑到前i-1个字符与前j个字符匹配的最小操作次数，在此基础上+1即可
在第i个字符后增加一个字符使之与前j个字符匹配，这个操作我们就要考虑到前i个字符与前j-1个字符相匹配的最小操作次数，我们只需要加上与第j个字符相同的字符即可，在此基础上+1即可
将第i个字符变成第j个字符，使之前i个字符与前j个字符匹配，这个操作我们就要考虑到前i-1个字符与前j-1个字符匹配的最小操作次数，在此基础上+1即可

初始化的过程我愿称之为精髓！！！
代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <string>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 1010, mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);

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

int main()
{
    scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
    //如果a序列为空，前i个字母对应的最小操作就此就是增加i个
    //如果b序列为空，前i个字母对应的最小操作就此就是删除i个
    for (int i = 0; i <= m; i ++ ) f[0][i] = i;
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            //第i个字符与第j个字符相同的话就不需要进行任何操作了
            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);
        }
    }

    printf("%d", f[n][m]);
    return 0;
}