线性动态规划（Linear-DP）是一种动态规划方法，它在状态转移时具有线性的特征。线性DP通常适用于那些线性的问题，它的状态并没有很复杂，一般状态转移方程也很简单，想题的思路也是非常快的。
在线性DP中，状态通常定义为一维数组dp[i]，表示目前在第i个阶段（例如数组的第i个元素）的最优解。状态转移方程依赖于前面的若干状态，例如dp[i] = f(dp[i-1], dp[i-2], ...)，其中f是某个函数，表示如何从前面的一个或多个状态得到当前状态的最优解。其中一位的状态只是一般的情况，下面例题为四维的情况，但是像这样的四维可谓少之又少。
线性DP的常见问题类型包括：
1. 最长递增子序列（LIS）：找到数组中最长递增子序列的长度。这个问题可以通过动态规划来解决，其中dp[i]表示以第i个元素结尾的最长递增子序列的长度 。
2. 最大子数组和：在数组中找到一个具有最大和的连续子数组。这个问题可以通过Kadane算法在线性时间内解决，但也可以用线性DP来解决 。
3. 最长公共子序列（LCS）：找到两个字符串的最长公共子序列。这个问题的状态转移方程是dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (if s1[i] == s2[j])) 。
4. 数字三角形：给定一个数字三角形，从顶部到底部找到路径，使得路径上的数字总和最大。这个问题可以通过动态规划来解决，其中dp[i][j]表示到达三角形第i行第j列的路径的最大和 。
5. 背包问题：在给定背包容量的情况下，从一组物品中选择一些物品，使得它们的总价值最大。虽然背包问题通常与线性DP无关，但某些背包问题的变体（如0/1背包问题）可以采用线性DP的方法解决。
线性DP问题的关键在于正确定义状态和状态转移方程，以及确定合适的初始条件和边界条件。通过这些定义，可以逐步构建出整个问题的最优解。
原题链接：312. 乌龟棋 - AcWing题库
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘只有一行，该行有 N 个格子，每个格子上一个分数（非负整数）。
棋盘第 1 格是唯一的起点，第 N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中共有 M 张爬行卡片，分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片），每种类型的卡片上分别标有 1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。
游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。
玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
输入格式
输入文件的每行中两个数之间用一个空格隔开。
第 1 行 2 个正整数 N 和 M，分别表示棋盘格子数和爬行卡片数。
第 2 行 N 个非负整数，a1,a2,……,aN，其中 ai 表示棋盘第 i 个格子上的分数。
第 3 行 M 个整数，b1,b2,……,bM，表示 M 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 M 张爬行卡片。
输出格式
输出只有 1 行，包含 1 个整数，表示小明最多能得到的分数。
数据范围
1≤N≤350,
1≤M≤120,
0≤ai≤100,
1≤bi≤4,
每种爬行卡片的张数不会超过 40。
输入样例：
9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1
输出样例：
73
解题思路：
此题标签是线性DP，暴力只可过两个样例点，此题DP状态的定义和描述是四维的定义，f[i][j][k][l]数组表示步数1用了i张步数2用了j张步数3用了k张步数4用了l张所获得最大分数，那么可以枚举步数的每一个状态，数组s统计卡牌步数的个数，最后求一下f[s[1]][s[2]][s[3]][s[4]]，既每一张卡牌都用完，那么到达任意一个格子，状态转移可以又四个状态转移过来，f[i][j][k][l]=max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+当前值。即到达f[i][j][k][l]，可以先走f[i-1][j][k][l]，留一张步数为1的卡牌留到最后使用到达此时的点（1+i+2*j+3*k+4*l），同理f[i][j-1][k][l]为留一张步数为2的卡牌到最后一步使用到达（1+i+2*j+3*k+4*l）点……
代码实现：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N =355,M=45; int n,m; int a[N],s[N];//a是分数数组，s[i]表示跳i步卡牌有s[i]张 int f[M][M][M][M]; //f[i][j][k][l]数组表示步数1用了i张步数2用了j张步数3用了k张步数4用了l张所获得最大分数 int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=m;i++){ int x; cin>>x; s[x]++; } f[0][0][0][0]=a[1];//初始为第一个格子，分数为第一个格子 for(int A=0;A<=s[1];A++){//分别枚举卡牌1，2，3，4的个数 for(int B=0;B<=s[2];B++){ for(int C=0;C<=s[3];C++){ for(int D=0;D<=s[4];D++){ int score=a[1+A+2*B+3*C+4*D];//可以到达点的分数 //前一个状态可以由少用1，2，3，4步的一张卡牌转移 if(A) f[A][B][C][D]=max(f[A][B][C][D],f[A-1][B][C][D]+score); if(B) f[A][B][C][D]=max(f[A][B][C][D],f[A][B-1][C][D]+score); if(C) f[A][B][C][D]=max(f[A][B][C][D],f[A][B][C-1][D]+score); if(D) f[A][B][C][D]=max(f[A][B][C][D],f[A][B][C][D-1]+score); } } } } cout<<f[s[1]][s[2]][s[3]][s[4]]<<endl; return 0; }
总结：
此种状态定义博主第一次遇到，最多的也就见过三维解决问题，像李白打酒，这个题状态的定义与描述很难想，开始寻思暴力能不能多拿点分，只能过两个样例，^—^，后来看了y总讲解，才知道用四维去定义，还是要多做题，DP问题只要能找到状态转移方程就基本解决了，博主感觉最难的还是状态的定义与描述。多做题积累经验，文章代码实现或者思路有错误的地方，请各位大佬指出，感激不尽*~*。
执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
