线性DP：递推方程有明显的线性的顺序。
考虑两个问题：如何状态表示（集合+属性）、如何状态计算（划分状态转移集合）
T1：

状态表示： 记录所有从起点走到(i,j)的路径中的路径数字之和的最大值。
状态计算：f[i,j] = max(f[i-1][j], f[i-1][j-1]) + a[i,j]
需要注意需要把f[i,j]初始化为极小值，避免算到三角形右边的元素。

T2：最长上升子序列

状态表示：使用一维数组，f[i]表示以第i个数结尾的上升子序列的长度的最大值。
状态计算：计算f[i]，去看倒数第二个数是哪个数，共i种可能，以编号1、2、3、……、i-1结尾或原本没有数（记为0）。每个循环先看是否满足上升的条件，若满足，则这个f[i]_j = f[j]+1，最后计算一个最大的f[i]_j就得出了f[i]的值。
时间复杂度计算：状态数量 × 转移的数量。此时是$n^2$。

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(){
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        f[i] = 1; //先全部赋值为1，只有a[i]一个数
        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;
}

如何保存最长序列？
创建一个数组g[i]，存储每个转移是怎么转移过来的（记录上一个状态的id，也就是找f[i,j]最大值时找到的位置）。

T3：最长公共子序列

状态表示：使用二维数组f[i,j]，表示的集合为所有第一个序列的前i个字母，和第二个序列的前j个字母构成的子序列，数组表示所有这些子序列的最大值。
状态计算：对于选不选a[i]、选不选b[j]，组合共有2×2种情况，f[i,j]是这些值取max。
所以都不选=f[i-1,j-1]，都选=f[i-1,j-1]+1，不选a选b的情况=f[i-1,j]，不选b选a的情况=f[i,j-1]。由于f[i-1,j]和f[i,j-1]都大于f[i-1,j-1]，说明已经涵盖了这种情况，所以比较最大值可以忽略这一项，即最后就三项。

#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(){
    cin >> n >> m;
    cin >> 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", f[n][m]);
}

T4：编辑距离
https://leetcode.cn/problems/edit-distance/description/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        int f[520][520];
        for(int i = 0; i <= 519; i++){
            f[i][0] = 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], min(f[i-1][j], f[i][j-1])) + 1;
                if(word1[i-1]==word2[j-1]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            }
        }
        return f[n][m];

    }
};

T5：石子合并（区间DP问题）

状态表示：f[i][j]表示所有将第i堆石子到第j堆石子合并成一堆石子的合并方式，表示的是这些合并方式的最小值。最终答案为f[1][N]。
状态计算：计算f[i][j]时，看从i到j之间从中间哪里划分（也就是最后一次合并时两堆石子原本的分界线位置），设k = j-i+1表示i到j的石子个数，则共有k-1个空可以划分，所以划分为k-1种情况。每种情况的结果=f[i,k]+f[k+1,j]+allweight_i_j，所以取这些值的最小值即可得到最终答案。
其中i到j全部重量可以用前缀和计算。通过递推式可以看出，循环的顺序应先为区间长度，再为开始位置。