线性DP

1 数字三角形

1.1 题目

数字三角形

1.2 分析

• 状态表示：f[i][j] 从起点走到(i,j)点的最大值

• 状态转移：来自左上方右上方

f[i][j] = max(f[i-1][j-1], f[i-1,j])+a[i][j]

#include <iostream>
using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[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 ++)
        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 ++)  // 第二行开始
        for (int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], 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 最长上升子序列

2.1 题目

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

2.2 分析

• 状态表示：f[i]表示以第i个数结尾的最大长度。

• 状态转移：上一个数是第k个数，k<i && a[k] < a[i]

f[i]=max{f[k]} + 1

#include <iostream>
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;
        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;
    return 0;
}

3 最长公共子序列

3.1 题目

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

3.2 分析

• 状态表示f[i][j]：表示A序列前i个字符和B序列前j个字符结束的最长公共子序列值。
• 状态转移：公共子序列是否包含a[i]，是否包含b[j]，总共四种情况
• 不包含a[i], b[j]可以表示为f[i-1][j-1]（这一类被三、四类涵盖了）
• 包含a[i], b[j]可以表示为f[i-1][j-1]+1
• 不包含a[i]，包含b[j]，可以用f[i-1][j]表示，但不完全等价
• 包含a[i]，不包含b[j]，可以用f[i][j-1]表示，但不完全等价

#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;
    scanf("%s%s", a + 1, b + 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;

}

4 最短编辑距离

4.1 题目

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

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

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

4.2 分析

• 状态表示f[i][j]：将a[1~i]变成b[1~j]的操作方式的最小次数

• 状态转移：最后一步的操作方式

• 删除字符a[i]，a[1~i-1]==b[1~j]，f[i-1][j]+1

• 增加字符，a[1~i]==b[1~j-1]，f[i][j-1]+1
• 修改字符，a[1~i-1]==b[1~j-1]，f[i-1][j-1]+1 or f[i-1][j-1]

f[i][j] = min{f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1/0}

#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 >> a + 1;
    cin >> m >> b + 1;


    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);
            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;

    return 0;
}