一、动态规划是什么？
在解决复杂问题时，暴力枚举法常常因为时间复杂度过高而导致程序效率低下。与此不同的是，动态规划（DP）提供了一种更加高效的方式——通过把原问题拆解为相对简单的子问题（状态），将原本需要反复计算的情况记录下来，以便在下一次遇到同一个子问题时直接查表，从而达到优化的效果。通常来说，使用动态规划解决问题需要定义清楚状态、状态转移方程和边界情况
下面是动态规划的两大核心性质，它们可以帮助我们判断这道题目是否可以利用动态规划来解决：
最优子结构：全局最优解包含子问题的最优解
无后效性：子问题决策不影响后续状态的定义方式
二、线性 DP
线性 DP 属于 DP 中最常见的一种，其状态转移是线性化的，第 i 个状态只依赖于前面若干个状态。定义清楚状态并且找到状态之间的依赖关系是解决问题的关键。下面以一道题目为例说明：
题目链接: link
P1115 最大子段和
题目描述
给出一个长度为n nn的序列a aa，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度n nn。
第二行有n nn个整数，第i ii个整数表示序列的第i ii个数字a i a_iai。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
7 2 -4 3 -1 2 -4 3输出 #1
4说明/提示
样例 1 解释
选取[ 3 , 5 ] [3, 5][3,5]子段{ 3 , − 1 , 2 } \{3, -1, 2\}{3,−1,2}，其和为4 44。
数据规模与约定
- 对于40 % 40\%40%的数据，保证n ≤ 2 × 10 3 n \leq 2 \times 10^3n≤2×103。
- 对于100 % 100\%100%的数据，保证1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^51≤n≤2×105，− 10 4 ≤ a i ≤ 10 4 -10^4 \leq a_i \leq 10^4−104≤ai≤104。
三、算法原理
本题要求解的是一段序列的最大子段和，通过暴力枚举法枚举序列的左右端点，我们可以很轻松地得出正确答案，但是非常遗憾，这种解法即使通过前缀和的优化也只是到达了 O(n^2)，1e10 级别的数据量将会超时。
经过观察，原问题可以被拆解为以 a[i] 结尾的最大子段和（状态），这样最终问题就变成了在所有数的最大子段和中选取最大的那一个结果。在以 a[i] 为结尾的最大子段和中，要么取之前最大子段和的结果和 a[i] 合并，要么清空最大子段和的结果，保留 a[i]，满足无后效性。
状态定义：设 f[i] 表示以第 i 个数结尾的连续子段的最大和。
状态转移方程：f[i] = max(f[i - 1] + a[i], a[i])
含义：以a[i]结尾的最大子段，要么是把a[i]接到前面以a[i-1]结尾的最大子段后面（如果前面的和是正贡献），要么是a[i]自己单独成段（如果前面的和是负贡献，不如舍弃）。
- 边界条件：f[1] = a[1]。
代码实现：
#include<iostream>usingnamespacestd;constintN=2e5+10;intf[N];inta[N];intmain(){intt;cin>>t;for(inti=1;i<=t;i++)cin>>a[i];f[1]=a[1];for(inti=1;i<=t;i++){f[i]=max(f[i-1]+a[i],a[i]);}intret=-0x3f3f3f3f;//结果有可能是负数，所以要足够小for(inti=1;i<=t;i++)ret=max(ret,f[i]);cout<<ret<<endl;return0;}手动模拟样例
序列：2 -4 3 -1 2 -4 3
| i | a[i] | f[i] = max(f[i-1]+a[i], a[i]) | ans |
|---|---|---|---|
| 1 | 2 | 2 | 2 |
| 2 | -4 | max(2-4, -4) = -2 | 2 |
| 3 | 3 | max(-2+3, 3) = 3 | 3 |
| 4 | -1 | max(3-1, -1) = 2 | 3 |
| 5 | 2 | max(2+2, 2) =4 | 4 |
| 6 | -4 | max(4-4, -4) = 0 | 4 |
| 7 | 3 | max(0+3, 3) = 3 | 4 |
最终答案为4，与样例输出一致。对应子段是[3, -1, 2]（下标 3~5）。
时间复杂度为 O(n)，只需遍历一次序列。
