在了解线性DP之前，我们首先要知道什么是动态规划，即为将一种复杂问题，分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。听起来比较抽象，动态规划简单来说就是确定问题的状态，通常题目都会提示，一般为“到第i个为止，xx为j(xx为k)的方案数/最小代价/最大价值 ，然后根据这个状态实时更新，得到最终状态，即为题目所求，接下来，我们通过讲解其中较为间的线性DP来更好的说明这个思想。
线性DP问题通常会将问题转化为一维数组的形式，将状态定义为以当前位置为结束点的最优解。状态转移方程往往只涉及到当前位置和前面位置的状态，并且计算过程是按顺序遍历数组逐步计算的。
我们通过一道例题来加深线性DP的思想，这道题首先有一个数字三角形。
从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。题目通俗易懂，对于最大和，那么有些人会想利用贪心，每次取路径中最大的点，那么最后的和是否最大呢，显然不行，会遇到先小后大的情况，所以贪心在本题并不适用，我们只需要每次得到路径的最大和，这个就是一个状态，然后不断遍历一个‘直角三角形，实时更新最大状态,最后特殊的一个状态为答案，根据此题，我们定义一个dp[N][N]，表示从(i,j)点往下路径的最大和，原二维数组为a[N][N]。
关键状态方程为
dp[i][j] = a[i][j] + max(dp[i+1][j],dp[i+1][j+1]);不断更新dp[i][j]，输出dp[1][1]即可，即为第一行第一列往下最大的，即为从端节点开始，即为题目所求。
具体题目链接如下：文章来源：https://www.toymoban.com/news/detail-825642.html
https://www.lanqiao.cn/problems/1536/learning/?page=1文章来源地址https://www.toymoban.com/news/detail-825642.html
到了这里，关于动态规划(DP)入门——线性DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
