线性DP-数字三角形模型
AcWing 898. 数字三角形
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

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

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i + 1; j++)  //每行最右边的点，是没有右上方的点，要初始化i + 1
            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]);

    printf("%d\n", res);
    return 0;
}
AcWing 1015. 摘花生
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j<= m; j++)
                scanf("%d", &w[i][j]);

        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]) + w[i][j];

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

    return 0;
}
AcWing 1018. 最低通行费
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 1e9;

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

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &w[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j= 1; j <= n; j++)
            if (i == 1 && j == 1) f[i][j] = w[i][j];
            else
            {
                f[i][j] = INF;
                if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }

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

    return 0;
}
AcWing 1027. 方格取数
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N * 2][N][N];

int main()
{
    scanf("%d", &n);

    int a, b, c;
    while (cin >> a >> b >> c && a || b || c) w[a][b] = c;

    for (int k= 2; k <= n + n; k++)
        for (int i1 = 1; i1 <= n; i1++)
            for (int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];
                    if (i1 != i2) t += w[i2][j2];

                    int &x = f[k][i1][i2];  //f[k][i1][i2]太长了，用一个引用来表示
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);  //下下
                    x = max(x, f[k - 1][i1 - 1][i2] + t);  //下右
                    x = max(x, f[k - 1][i1][i2 - 1] + t);  //右下
                    x = max(x, f[k - 1][i1][i2] + t);      //右右
                }
            }

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

    return 0;
}
AcWing 275. 传纸条
#include <iostream>

using namespace std;

const int N = 55;

int n,m;
int g[N][N];
int f[N * 2][N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    for (int k = 2; k <= n + m; k++)
        for (int i = max(1, k - m); i <= n && i < k; i++)
            for (int j = max(1, k - m); j <= n && j < k; j++)
                for (int a = 0; a <= 1; a++)
                    for (int b = 0; b <= 1; b++)
                    {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m)
                        {
                            t += g[j][k - j];
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                        }
                    }

    cout << f[n + m][n][n] << endl;  //f(k, x1, x2)

    return 0;
}
线性DP-最长上升子序列模型
AcWing 895. 最长上升子序列
1≤N≤1000，
−109≤数列中的数≤109

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //下标从1开始

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

    printf("%d\n", res);

    return 0;
}
AcWing 896. 最长上升子序列 II
1≤N≤100000，
−109≤数列中的数≤109

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N]; //不同长度下，所有上升子序列结尾的最小值

int main()
{
    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++)  //二分出来小于某个数的最大的数
    {                            //二分出来小于a[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找的是能接到哪个数的后面
        q[r + 1] = a[i]; //r是小于a[i]的最后一个数，r+1 是大于等于a[i]的
    }

    printf("%d\n", len);

    return 0;
}
AcWing 897. 最长公共子序列
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &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);
        }
    printf("%d\n", f[n][m]);

    return 0;
}