线性DP

数字三角形

用f[i] [j]表示走到f[i] [j]的最大步数，一共只有两种走法，左上方走下来或右上方走下来，因此我们可以列出状态转移方程

f[i][j] = f[i - 1][j - 1] + a[i][j]; //左上方走下来
f[i][j] = f[i - 1][j] + a[i][j]; //右上方走下来

所以我们只要找到所有点的走法的最大值，再枚举最后一行，也就是出口处的最大值，就是整个三角型的最大值。

#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=0x3f3f3f3f;
int f[N][N];
int a[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=1;i<=n;i++){             
        for(int j=0;j<=i+1;j++){          //因为有负数，所以应该将两边也设为-INF
            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]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);
        }
    }

    int res=-INF;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
}

逆序写法，更简单

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int f[N][N];
int 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; i >= 1; i -- ){
        for (int j = i; j >= 1; j -- ){
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
        }
    }

    cout << f[1][1] << endl; // 自下向上一路选最大值选出来的

    return 0;
    
}

最长上升子序列

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

状态转移方程

if (w[i] > w[j])
    f[i] = max(f[i], f[j] + 1);

对于每个i，我们都枚举所有小于w[i]的w[j]，找出最大的小于w[i]的以w[j]为结尾的f[j]。但最后的点不一定是最大的点，我们还需要遍历一遍，找到f[i]的最大值。

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];

    int mx = 1;    // 找出所计算的f[i]之中的最大值，边算边找
    for (int i = 0; i < n; i++) {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = 0; j < i; j++) {
            if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
        }
        mx = max(mx, f[i]);
    }

    cout << mx << endl;
    return 0;
}

这是一个O(n^2)的做法，对于过大的数据仍然会超时。

优化（DP+二分）

状态表示：f[i]表示长度为i的单调增子序列中最后一位最小的数字。

如果当前的w[i]比f[cnt - 1]大，说明满足一个单调增的序列，就将他变成当前序列的最后一个数（不一定是最小的），同时cnt++。

如果当前w[i]比f[cnt - 1]小，说明找到一个更好的序列，可以将之前的序列更新，让这个更小的数成为当前的最后一个数。

对于查找，我们可以用二分法找到第一个大于等于w[i]的数字

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    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;
        }
        len = max(len, r + 1); //r存的是长度，r + 1表示r的下一个位置
        q[r + 1] = a[i]; // 更新
    }
    
    cout << len << endl;

    return 0;
}

最长公共子序列

状态划分：两个序列末尾的字符是否相等。

f[i][j] = max(f[i - 1][j], f[i][j - 1]); // 末尾字符不相等
f[i][j] = f[i - 1][j - 1] + 1; // 末尾字符相等

这里摘一下大佬的题解吧：


#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
  cin >> n >> m >> a + 1 >> b + 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] + 1;
      } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  cout << f[n][m] << '\n';
  return 0;
}

LCS+输出字符串

scanf("%s%s", s + 1, t + 1);
    //cout << strlen(s + 1) << ' ' << strlen(t + 1) << endl;
    for (int i = strlen(s + 1); i >= 1; i -- ){
        for (int j = strlen(t + 1); j >= 1; j -- ){
            if (s[i] == t[j]) f[i][j] = f[i + 1][j + 1] + 1;
            else f[i][j] = max(f[i + 1][j], f[i][j + 1]);
        }
    }
    int i = 1, j = 1;
    while (i <= strlen(s + 1) && j <= strlen(t + 1)){
        if (s[i] == t[j]){
            cout << s[i];
            i ++;
            j ++;
        }
        else if (f[i][j] == f[i + 1][j]) i ++ ;
        else j ++;
    }

最短编辑距离

状态表示f[i] [j] ：所有将a[1 ~ i] 变成b[1 ~ j] 的操作方式。

属性：min。

状态计算：

（1）删除：若要从a中删除一个字符，则需要让f[1 ~ i - 1] 与 f[1 ~ j] 匹配，因此

f[i][j] = f[i - 1][j] + 1;

（2）增加：从a中增加一个字符，需要让f[1 ~ i]与f[i ~ j - 1] 匹配

f[i][j] = f[i][j - 1] + 1;

（3）修改：将f[i]改成f[j]，让前面的各位刚好匹配

f[i][j] = f[i - 1][j - 1] + 1; // f[i] != f[j]
f[i][j] = f[i - 1][j - 1]; // f[i] == f[j]

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

    for (int i = 0; i <= n; i ++ ) f[i][0] = i;
    for (int i = 0; i <= m; i ++ ) f[0][i] = 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;
}

最长公共上升子序列

LIS+LCS的混合问题。

状态表示：

f[i] [j] 代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；
f[i] [j]的值等于该集合的子序列中长度的最大值；
状态计算（对应集合划分）：

首先依据公共子序列中是否包含a[i]，将f[i] [j]所代表的集合划分成两个不重不漏的子集：

不包含a[i]的子集，最大值是f[i - 1] [j]；
包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：
子序列只包含b[j]一个数，长度是1；
子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1] [1] + 1；
…
子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1] [j - 1] + 1；
如果直接按上述思路实现，需要三重循环：

for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (a[i] == b[j])
        {
            int maxv = 1;
            for (int k = 1; k < j; k ++ )
                if (a[i] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);
            f[i][j] = max(f[i][j], maxv);
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3010;
int a[maxn], b[maxn];
int f[maxn][maxn];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];

    for (int i = 1; i <= n; i ++ ){
        int maxv = 1;
        for (int j = 1; j <= n; j ++ ){
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) ans = max(ans, f[n][i]);
    cout << ans << endl;
}