线性dp通常采用递推方式实现。
线性dp包含如下含义：
1、在线性空间上进行dp（一般是一维、二维数组），所以树型dp不是线性dp；
2、递推是在各个维度上沿着固定方向线性变化，所以区间dp不是线性dp。
实例分析（数塔问题是线性dp，而数岭问题不是线性dp）：这两个问题都是在二维线性空间（二维数组）上进行dp，但是递推的方向投影到两个坐标轴上会发现，数塔问题在坐标轴上是沿着固定方向线性变化，而数岭问题在坐标轴上有时正方向变化有时负方向变化，所以数岭问题不是线性dp。
下面的例题都是朴素线性dp，朴素线性dp的状态设计与线性空间相对应，一维空间就是一维状态，二维空间就是二维状态，并且每个状态就是线性空间中对应位置的某个属性。另外还可以在两个一维线性空间上dp，状态要设计成二维的，但实际上只是两个一维状态的拼接（如：最长公共子序列、最短编辑距离）。
A[1] A[2] A[3] ...... A[n]
求该序列的连续子序列的和的最大值。
将问题用n个集合属性来表达，即以A[i]（1 $\leqslant$ i $\leqslant$ n）结尾的连续子序列的最大和，
这n个最大和的最大值就是问题的解，A[n]集合成为树的根结点，也是集合A[i]（1 $\leqslant$ i $\leqslant$ n-1）的祖先结点。
原子集合属性（以A[i]，1 $\leqslant$ i $\leqslant$ n，结尾的单一元素子序列最大和）可以直接得出为A[i]。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i] = max \left\{ \begin{aligned} &A[i]&&\text{(A[i]不与以A[i-1]结尾的连续子序列组成新的连续子序列)}\\ &f[i-1]+A[i]&&\text{(A[i]与以A[i-1]结尾连续子序列组成新的连续子序列)} \end{aligned} \right.\]// 原子集合初始化：f[i] = A[i] (1<=i<=n)
for (int i = 2; i <= n; i++)
f[i] = max(f[i], f[i-1] + A[i]);
// 最终结果：max(f[i]) (1<=i<=n)
A[1] A[2] A[3] ...... A[n]
求该序列的有序子序列的最大长度（有序可以是不下降，上升，不上升，下降，这里以上升为例）。
将问题用n个集合属性来表达，即以A[i]（1 $\leqslant$ i $\leqslant$ n）结尾的上升子序列的最大长度，
这n个最大长度的最大值就是问题的解，A[n]集合成为树的根结点，也是集合A[i]（1 $\leqslant$ i $\leqslant$ n-1）的祖先结点。
原子集合属性（以A[i]，1 $\leqslant$ i $\leqslant$ n，结尾的没有前序元素的上升子序列的最大长度）可以直接得出为1。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i] = max \left\{ \begin{aligned} &1&&\text{(A[i]没有前序元素)}\\ &f[j]+1, 1\leqslant j<i&&\text{(A[i]前序元素为A[j])} \end{aligned} \right.\]// 原子集合初始化：f[i] = 1 (1<=i<=n)
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
if (A[i] > A[j])
f[i] = max(f[i], f[j] + 1);
// 最终结果：max(f[i]) (1<=i<=n)
最长有序子序列问题还可以优化，不过不再是动态规划的范畴，详见贪心一文。
A[1] A[2] A[3] ...... A[m]
B[1] B[2] B[3] ...... B[n]
求两个序列的公共子序列的最大长度。
将问题的解用序列A前m个元素序列和序列B前n个元素序列的所有公共子序列的最大长度这一集合属性来表达。
原子集合属性（序列A前0个元素序列和序列B前j个元素序列，1 $\leqslant$ j $\leqslant$ n，的所有公共子序列最大长度、序列A前i个元素序列，1 $\leqslant$ i $\leqslant$ m，和序列B前0个元素序列的所有公共子序列最大长度）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = max \left\{ \begin{aligned} &f[i-1][j-1]+1&&\text{(选A[i]和B[j]，即A[i]==B[j])}\\ &max\{f[i-1][j], f[i][j-1]\}&&\text{(不选A[i]或不选B[j]，即A[i]!=B[j])} \end{aligned} \right.\]// 原子集合初始化：f[i][0] = f[0][j] = 0 (1<=i<=m, 1<=j<=n)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i] == A[j])
f[i][j] = f[i-1][j-1] + 1;
else
f[i][j] = max(f[i-1][j], f[i][j-1]);
}
}
// 最终结果：f[m][n]
A[1] A[2] A[3] ...... A[m]
B[1] B[2] B[3] ...... B[n]
求将序列A变为序列B的最少编辑步数（编辑操作包括插入、删除和修改三种）。
将问题的解用将序列A前m个元素序列编辑成序列B前n个元素序列的最少步数这一集合属性来表达。
原子集合有两种：第一种（将序列A前i个元素序列，1 $\leqslant$ i $\leqslant$ m，编辑成序列B前0个元素序列的最少步数）属性可以直接得出为i；第二种（序列A前0个元素序列编辑成序列B前j个元素序列，1 $\leqslant$ j $\leqslant$ n，的最少步数）属性可以直接得出为j。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[i][j] = min \left\{ \begin{aligned} &min\{f[i-1][j]+1, f[i][j-1]+1\}&&\text{(将A[i]删除或插入)}\\ &f[i-1][j-1]&&\text{(A[i]==B[j]，A[i]不需要修改)}\\ &f[i-1][j-1]+1&&\text{(A[i]!=B[j]，将A[i]修改为B[j])} \end{aligned} \right.\]// 原子集合初始化：f[i][0] = i (1<=i<=m), f[0][j] = j (1<=j<=n)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; 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);
}
}
// 最终结果：f[m][n]